P6508 [CRCI2007-2008] KUHAR

To cook a certain dish, you need $n$ kinds of ingredients. For the $i$-th ingredient, one dish requires $a_i$ units, and the kitchen currently has $b_i$ units. For each ingredient, you can buy more from the supermarket. There are two package types: **small** and **large**. For the $i$-th ingredient, a small package contains $sm_i$ units and costs $pm_i$ yuan per package; a large package contains $sv_i$ units and costs $pv_i$ yuan per package. For each ingredient, you may buy any number (possibly zero) of small and large packages. You have $m$ yuan. Find the maximum number of dishes you can cook with this money.

The first line contains two integers: the number of ingredients $n$ and the amount of money $m$. Lines $2$ to $(n + 1)$ each contain six integers. Line $(i + 1)$ contains $a_i, b_i, sm_i, pm_i, sv_i, pv_i$, with meanings as described in the **Description**.

Output one integer in a single line, the maximum number of dishes you can cook.

#### Constraints For all testdata, it is guaranteed that: - $1 \leq n \leq 100$, $1 \leq m \leq 10^5$. - $10 \leq a_i \leq 100$, $1 \leq b_i \leq 100$. - $1 \leq sm_i \lt sv_i \leq 100$, $1 \leq pm_i \lt pv_i \leq 100$. #### Notes **This problem is translated from [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T3 KUHAR***。 Translated by ChatGPT 5