Bomb Production

Hyojin needs fixed numbers of N different components to make one bomb. Some components are already stored in a warehouse, and any shortage can be bought from a market using at most M dollars.

For each component, the market sells two package types: a small package and a large package. Hyojin may buy any nonnegative number of either package type, and the package sizes and prices may differ by component.

Find the maximum number of bombs that can be made without exceeding the budget.

The first line contains two integers N and M (1 <= N <= 100, 1 <= M <= 100000), the number of component types and the budget.

Each of the next N lines contains six positive integers describing one component: X, Y, SM, PM, SV, and PV.

• X: the number of this component required for one bomb (10 <= X <= 100)
• Y: the number of this component already in the warehouse (1 <= Y <= 100)
• SM: the number of components in one small package (1 <= SM < 100)
• PM: the price of one small package (10 <= PM < 100)
• SV: the number of components in one large package (SM < SV <= 100)
• PV: the price of one large package (PM < PV <= 100)

Print the maximum number of bombs Hyojin can make by spending at most M dollars.

In the first visible test case, buying 3 small packages and 1 large package of the first component, and 1 small package and 2 large packages of the second component, costs 99 dollars.

The warehouse then has 51 units of the first component and 60 units of the second component, enough to make 5 bombs.