Counter Strike

Time Limit: 5 Seconds    Memory Limit: 32768 KB

In Counter Strike, each team member can buy a large gun, a pistol and some bullets. One clip of bullets will be bought with the gun, and additional bullets should be bought in clips. There is a limit on each kind of bullets so that you can't buy arbitrary number of clips. Each gun has a fixed damage. The HP of each enemy is initially 100.

OldBig is a terrorist who is real sharp and never wastes any bullet. At the beginning of the game, OldBig has nothing but money. He has some choices in buying guns and bullets. He wants to know how many enemies he could kill if he makes a wise choice.

Input

This problem contains multiple tests. Each test starts with two positive integers n ( 1 <= n <= 40 ) and m ( 1 <= m <= 16000 ). n is the number of different guns, and m is the sum of money available. The following n lines contain 6 integers each, specifying information for each type of guns, in the order as follows:

> a: damage ( 1 <= a <= 300 )
> b: price of the gun ( 1 <= b <= 16000 )
> c: price of one clip of bullets ( 1 <= c <= 16000 )
> d: maximum clips of bullets you can buy ( 0 <= d <= 10 )
> e: number of bullets in each clip ( 1 <= e <= 100, 0 <= d*e <= 300 )
> f: type of gun, f = 1 means large gun, f = 2 means pistol

A test with n = 0 indicates the end of input, and this test should not be processed.

Output

One integer on a single line for each test, the maximum number of enemies OldBig could kill.

Sample Input

2 4000
20 1000 200 3 30 1
20 2000 200 3 30 2

3 4000
20 1000 200 3 30 1
20 2000 200 3 30 1
20 2200 200 3 30 2

0

Sample Output

42
36

Submit

Source: ZOJ Monthly, December 2002