VMSS '15 #5 - Jeffrey and Frank and a Lack of Roads

Points: 12

Time limit: 2.5s

Memory limit: 256M

Authors:

Problem type

Frank has made it to a Food Basics! Without causing property damage exceeding $1000! There he meets Jeffrey (since grocery stores don't have roads) and he agrees to help Frank buy some apples. You must also help Frank buy some apples.

The Food Basics that Frank is visiting has $N$ $N$ different types of apples, and he can take as much as he can of each type. However, there are some restrictions: Frank has only $R$ $R$ dollars to spend on apples, and his car can only hold $S$ $S$ volume, excluding Frank's volume (Frank obviously isn't giving Jeffrey a ride, as cars drive on roads).

Frank also likes some types of apples more than others, and he assigns a value $V$ $V$ to each type of apple. Frank likes apples with larger values.

Jeffrey and Frank would like to buy apples in such a way so that he can maximize the total sum of all values of apples. Help them calculate it!

Input Specification

The first line of input will contain the integers $N$ $N$ $(1 \le N \le 10)$ $(1 \leq N \leq 10)$ , $R$ $R$ , and $S$ $S$ $(1 \le R, S \le 1\,000)$ $(1 \leq R, S \leq 1 000)$ .

The next $N$ $N$ lines will each denote a type of apple and be in the form E V A B, where $E$ $E$ is the name of the apple type, $V$ $V$ $(1 \le V \le 1\,000)$ $(1 \leq V \leq 1 000)$ is the value given to the type of apple, $A$ $A$ $(1 \le A \le R)$ $(1 \leq A \leq R)$ is the cost of one of these apples in dollars, and $B$ $B$ $(1 \le B \le S)$ $(1 \leq B \leq S)$ is the volume that one of these apples takes up.

It is guaranteed that the apples will be given in alphabetical order by name. Apple names will be strings of Latin characters, without spaces. Each apple name will not exceed $32$ $32$ characters in length. Each type of apple will have a unique name.

Output Specification

First, print out the maximum value sum of apples that Frank can buy. Then, for each type of apple (in alphabetical order), print out a line with the apple type and the number of apples Frank should buy to maximize value.

If there are multiple answers, print any of them.

Sample Input

Copy

3 250 250
gala 500 20 4
goldendelicious 450 1 25
green 380 13 4

Sample Output

Copy

10110
gala 1
goldendelicious 7
green 17

Sample Explanation

In order to maximize the value of apples purchased, Jeffrey and Frank should buy seven goldendelicious apples, 17 green apples, and 1 gala apple. The sum of the values of the apples they buy will be $10\,110$ $10 110$ .

Comments

1
andi_g commented on Aug. 14, 2016, 4:34 p.m.
If in order to maximize the value of their apples, they shouldn't buy one of the apples, should you include that in your output? For example, if they needed 0 gala apples, 7 golden delicious, and 17 green would the output be:

Copy
gala 0 goldendelicious 7 green 17

0

Pleedoh commented on Sept. 4, 2017, 11:47 p.m.

For those who still care

Then, for each type of apple (in alphabetical order) print out a line with the apple type and the number of apples Frank should buy to maximise value.

Yes, I believe so.