E - Sensor Optimization Dilemma 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

ある製品の製造には 1,2,\dots,N の番号が付いた N 個の工程が必要です。

各工程 i について、それを処理する 2 種類の機械 S_i,T_i が売られています。

  • 機械 S_i : 1 台につき 1 日あたり製品 A_i 個分の処理ができ、 1 台 P_i 円で導入できる
  • 機械 T_i : 1 台につき 1 日あたり製品 B_i 個分の処理ができ、 1 台 Q_i 円で導入できる

それぞれの機械は 0 台以上何台でも導入できます。

機械の導入の結果、工程 i を 1 日あたり製品 W_i 個分処理できるようになったとします。
このとき、製造能力を W の最小値、すなわち \displaystyle \min^{N}_{i=1} W_i と定義します。

全体の予算が X 円のとき、達成可能な製造能力の最大値を求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 100
  • 1 \le A_i,B_i \le 100
  • 1 \le P_i,Q_i,X \le 10^7

入力

入力は以下の形式で標準入力から与えられる。

N X
A_1 P_1 B_1 Q_1
A_2 P_2 B_2 Q_2
\vdots
A_N P_N B_N Q_N

出力

答えを整数として出力せよ。

入力例 1

3 22
2 5 3 6
1 1 3 3
1 3 2 4

出力例 1

4

例えば、次の通り機械を導入することで製造能力を 4 にすることができ、これが達成可能な最大値です。

  • 工程 1 に対し機械 S_1 を 2 台導入する。
    • 1 日あたり製品 4 個分の処理に相当し、導入に合計 10 円かかる。
  • 工程 2 に対し機械 S_2 を 1 台導入する。
    • 1 日あたり製品 1 個分の処理に相当し、導入に合計 1 円かかる。
  • 工程 2 に対し機械 T_2 を 1 台導入する。
    • 1 日あたり製品 3 個分の処理に相当し、導入に合計 3 円かかる。
  • 工程 3 に対し機械 T_3 を 2 台導入する。
    • 1 日あたり製品 4 個分の処理に相当し、導入に合計 8 円かかる。

入力例 2

1 10000000
100 1 100 1

出力例 2

1000000000

入力例 3

1 1
1 10000000 1 10000000

出力例 3

0

正の製造能力が得られない場合もあります。

入力例 4

10 7654321
8 6 9 1
5 6 4 3
2 4 7 9
7 8 9 1
7 9 1 6
4 8 9 1
2 2 8 9
1 6 2 6
4 2 3 4
6 6 5 2

出力例 4

894742

Score : 475 points

Problem Statement

The manufacturing of a certain product requires N processes numbered 1,2,\dots,N.

For each process i, there are two types of machines S_i and T_i available for purchase to handle it.

  • Machine S_i: Can process A_i products per day per unit, and costs P_i yen per unit.
  • Machine T_i: Can process B_i products per day per unit, and costs Q_i yen per unit.

You can purchase any number of each machine, possibly zero.

Suppose that process i can handle W_i products per day as a result of introducing machines.
Here, we define the production capacity as the minimum of W, that is, \displaystyle \min^{N}_{i=1} W_i.

Given a total budget of X yen, find the maximum achievable production capacity.

Constraints

  • All input values are integers.
  • 1 \le N \le 100
  • 1 \le A_i,B_i \le 100
  • 1 \le P_i,Q_i,X \le 10^7

Input

The input is given from Standard Input in the following format:

N X
A_1 P_1 B_1 Q_1
A_2 P_2 B_2 Q_2
\vdots
A_N P_N B_N Q_N

Output

Print the answer as an integer.

Sample Input 1

3 22
2 5 3 6
1 1 3 3
1 3 2 4

Sample Output 1

4

For example, by introducing machines as follows, we can achieve a production capacity of 4, which is the maximum possible.

  • For process 1, introduce 2 units of machine S_1.
    • This allows processing 4 products per day and costs a total of 10 yen.
  • For process 2, introduce 1 unit of machine S_2.
    • This allows processing 1 product per day and costs a total of 1 yen.
  • For process 2, introduce 1 unit of machine T_2.
    • This allows processing 3 products per day and costs a total of 3 yen.
  • For process 3, introduce 2 units of machine T_3.
    • This allows processing 4 products per day and costs a total of 8 yen.

Sample Input 2

1 10000000
100 1 100 1

Sample Output 2

1000000000

Sample Input 3

1 1
1 10000000 1 10000000

Sample Output 3

0

There may be cases where a positive production capacity cannot be achieved.

Sample Input 4

10 7654321
8 6 9 1
5 6 4 3
2 4 7 9
7 8 9 1
7 9 1 6
4 8 9 1
2 2 8 9
1 6 2 6
4 2 3 4
6 6 5 2

Sample Output 4

894742