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~ 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~ dollars to spend on apples, and his car can only hold ~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~ 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 maximise the total sum of all values of apples. Help them calculate it!
The first line of input will contain the integers ~N~ ~(1 \leq N \leq 10)~, ~R~, and ~S~ ~(1 \leq R, S \leq 1\,000)~.
The next ~N~ lines will each denote a type of apple and be in the form
E V A B, where ~E~ is the name of the apple type, ~V~ ~(1 \leq V \leq 1\,000)~ is the value given to the type of apple, ~A~ ~(1 \leq A \leq R)~ is the cost of one of these apples in dollars, and ~B~ ~(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 characters in length. Each type of apple will have a unique name.
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 maximise value.
If there are multiple answers, print any of them.
3 250 250 gala 500 20 4 goldendelicious 450 1 25 green 380 13 4
10110 gala 1 goldendelicious 7 green 17
In order to maximise 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~.