题目描述

做某种菜需要 $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$，其含义见【题目描述】。

输出格式

输出一行一个整数，表示你最多能做出几道该菜品。

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

5

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

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 Regional Competition T3 KUHAR。