Trapped at home in quarantine, Johan tries to keep madness at bay and fend off isolation by playing Critter Junction, a social simulation video game. One of the main aspects of the game is collecting and harvesting various types of resources, in order to gain Bling, the currency of the game. Johan specializes in running the fruit% category of the game, in which the goal is to obtain the maximum amount of Bling in $40$ days using only fruits and no other resources. 

Each fruit can be sold for $100$ Bling, or planted to become a fruit tree (but not both). Every three days, starting on the third day after it was planted, a fruit tree yields three new fruits.

There are also some more exotic fruits that can be bought from the neighboring village. Once per day, the player can travel to the neighboring village and pay $400$ Bling to buy a single exotic fruit which you can then plant or sell already on the same day. Analogously to normal fruits, these exotic fruits can be planted into exotic fruit trees which yield three exotic fruits every three days. Each exotic fruit can be sold for $500$ Bling.

Any number of fruits/exotic fruits can be harvested, sold and planted during a day (subject to availability of course, e.g. it is not possible to sell more fruits than you actually have), but at most a single exotic fruit can be bought. These activities can be done in any order, so it is for instance possible within the same day to first harvest a few fruits (exotic or not), then sell those fruits for Bling, then use that Bling to buy an exotic fruit, and then either plant or sell that exotic fruit.

Given the current state of Johan’s fruit farm, what is the maximum amount of Bling he can achieve in the remaining time?

-----Input-----
The input consists of a single line containing six integers $d$, $b$, $f$, $t_0$, $t_1$ and $t_2$ ($1 \le d \le 40$, $0 \le b \le 500$, and $0 \le f, t_0, t_1, t_2 \le 100$), where:
 - $d$ is the number of remaining days Johan has
 - $b$ is the current amount of Bling Johan has.
 - $f$ is the current number of fruits Johan has.
 - $t_ i$ is the number of fruit trees Johan has that will yield crop $i$ days from today (for $0 \le i \le 2$).

Johan currently does not have any exotic fruits or exotic fruit trees.

-----Output-----
Output a single integer: the maximum amount of Bling Johan can have after playing $d$ days.

-----Examples-----
Sample Input 1:
4 0 1 0 0 0
Sample Output 1:
300

Sample Input 2:
5 0 1 0 1 0
Sample Output 2:
1900

Sample Input 3:
6 0 1 1 0 0
Sample Output 3:
2300

Sample Input 4:
10 399 0 0 0 0
Sample Output 4:
399

Source: kattis | Difficulty: HARD


Solutions: