题目描述

做某种菜需要$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中，99元买3小包和一大包第一种源料，1小包和2大包第二种源料。价格 (3•10 + 1•11 + 1•10+ 2•24 = 99).则有51 units (8 + 3•10 + 1•13) 第一种源料和 60 units (20 + 1•6 + 2•17)第二种源料。可以做5份。

数据规模与约定

对于全部的测试点，保证：
-$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$。