[ABC374] E - Sensor Optimization Dilemma 2

E - Sensor Optimization Dilemma 2

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：475分

题面

生产某种产品需要个编号为的工序。

对于每个工序，都可以购买两种类型的机器和来进行处理。

• 机器：每台每天可以处理个产品，成本为每台日元。
• 机器：每台每天可以处理个产品，成本为每台日元。

你可以购买任意数量的每种机器，也可以不购买。

假设引入机器后，工序可以每天处理个产品。
这里，我们将生产能力定义为的最小值，即。

给定总预算为日元，找出最大可实现的生产能力。

限制条件

• 所有输入值均为整数。

---

输入

输入从标准输入中按以下格式给出：

输出

输出一个整数作为答案。

---

输入样例1

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

输出样例1

4

例如，通过引入以下机器，我们可以实现生产能力为4，这是可能的最大值。

• 对于工序1，引入2台机器。
  • 这样每天可以处理4个产品，总成本为10日元。
• 对于工序2，引入1台机器。
  • 这样每天可以处理1个产品，总成本为1日元。
• 对于工序2，引入1台机器。
  • 这样每天可以处理3个产品，总成本为3日元。
• 对于工序3，引入2台机器。
  • 这样每天可以处理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