[CRCI2007-2008] KUHAR
题目描述
做某种菜需要 $n$ 种食材,对于第 $i$ 种食材,做一道该菜品需要 $a_i$ 份该食材,目前厨房已经有 $b_i$ 份该食材。对于每种食材都可以去超市再买一些,超市里有**大包**和**小包**两种类型,第 $i$ 种食材的小包每包有 $sm_i$ 份该食材,价格为每包 $pm_i$ 元,大包有 $sv_i$ 份该食材,价格为每包 $pv_i$ 元。对于每种食材,你都可以买任意多包(可以不买)的大包与小包。
你手里有 $m$ 元钱,现在请求出用你手中的钱,最多能做出几道该菜品。
输入输出格式
输入格式
输入的第一行有两个整数,分别表示食材数 $n$ 和你的钱数 $m$。
第 $2$ 到第 $(n + 1)$ 行,每行六个整数,第 $(i + 1)$ 行的整数分别为 $a_i, b_i, sm_i, pm_i, sv_i, pv_i$,其含义见【题目描述】。
输出格式
输出一行一个整数,表示你最多能做出几道该菜品。
输入输出样例
输入样例 #1
2 100
10 8 10 10 13 11
12 20 6 10 17 24
输出样例 #1
5
输入样例 #2
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
输出样例 #2
2
说明
#### 数据规模与约定
对于全部的测试点,保证:
- $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$。
#### 说明
**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T3 KUHAR***。