Problem Description

A school has just finished its sports meet and is preparing to award as many students as possible with a prize. Each prize consists of \( N \) items, such as 5 pencils, 10 exercise books, etc. Each prize is identical. Although the school's storage room still has some leftover items from last year's sports meet. In the store, there are plenty of each item, but they are only available in two types of packages: large or small, and they cannot be bought individually.

The problem is to maximize the number of such prizes that can be prepared using \( M \) yuan.

Input Format

The first line contains two integers: \( N \) and \( M \).

The following \( N \) lines each contain six positive integers \( x, y, sm, pm, sv, pv \), representing the relevant data for one item:

• \( x \): the number of this item required in one prize.
• \( y \): the number of this item leftover from last year.
• \( sm \): the number of items in a small package.
• \( pm \): the price of a small package.
• \( sv \): the number of items in a large package.
• \( pv \): the price of a large package.

Output Format

A single integer representing the maximum number of prizes that can be prepared.

Sample Input and Output

Input Sample #1

2 100
10 8 10 10 13 11
12 20 6 10 17 24

Output Sample #1

5

Input Sample #2

3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16

Output Sample #2

2

Notes

For all data, the following constraints are satisfied:

\( 1 \le N \le 100 \), \( 1 \le M \le 10^5 \).

\( 10 \le x, pm \le 100 \), \( 1 \le y, sm \le 100 \), \( sm < sv \le 100 \), \( pm < pv \le 100 \).

见题面 Input 部分

见题面 Output 部分