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 different types of apples, and he can take as much as he can of each type. However, there are some restrictions: Frank has only dollars to spend on apples, and his car can only hold 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 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 , , and .

The next lines will each denote a type of apple and be in the form `E V A B`

, where is the name of the apple type, is the value given to the type of apple, is the cost of one of these apples in dollars, and 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 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

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

#### Sample Output

```
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 .

## Comments

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:

For those who still careYes, I believe so.