P5878 Prizes

The school has just finished its sports meeting and plans to give awards to as many students as possible, giving each person a prize. Each prize contains $N$ kinds of items, such as $5$ pencils, $10$ exercise books, and so on. Every prize is exactly the same. The school storeroom still has some items left over from last year’s sports meeting. In the store, there are plenty of each kind of item, but there are only two types of packaging: a large box or a small box, and you must buy whole boxes without opening them. Now the problem is: with this $M$ yuan, making full use of the money, what is the maximum number of such prizes that can be prepared?

The first line contains two integers: $N, M$. Then there are $N$ lines. Each line contains six positive integers $x, y, sm, pm, sv, pv$, describing one kind of item: - $x$: the number of this item needed in one prize. - $y$: the number of this item left over from last year. - $sm$: the number of this item in one small box. - $pm$: the price of one small box of this item. - $sv$: the number of this item in one large box. - $pv$: the price of one large box of this item.

Output one integer: the maximum number of prizes that can be prepared.

For all testdata, it holds that: $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$. Translated by ChatGPT 5