Alice has recently become fascinated with Plants vs. Zombies (Sunflower Edition).

There are two types of sunflowers: the -th type requires sun to plant and generates sun per round.

Initially, you have sun.

At the beginning of each round, you can buy and plant each type of sunflower at most once. At the end of each round, you will get all the sun generated by your sunflowers planted in this and previous rounds.

Assuming you can plant an unlimited number of sunflowers, calculate the maximum amount of sun you can have after rounds.

输入描述:

The first line contains two integers  and  (), representing the initial amount of sun you have and the number of rounds the game will be played.

The second line contains two integers  and  (), describing the attributes of the first type of sunflower.

The third line contains two integers  and  (), describing the attributes of the second type of sunflower.

输出描述:

Output a single integer, which is the maximum amount of sun you can have after  rounds.

75 3
50 25
25 15

125

50 4
25 15
50 25

125

备注:

In the first sample test case, Alice starts with  sun and has  rounds to plant sunflowers. Here is the optimal strategy:
In the first round, spend  sun to plant both types of sunflowers. At the end of the round,  sun would be generated.
In the second round, spend  sun to plant the second type of sunflower and keep  sun. At the end of the round,  sun would be generated, and your sun would increase to .
In the third round, do not buy new sunflowers. After collecting  sun for this round, you would have  sun.