One of Japan's distinctive features are the millions of vending machines spread all over the country. You happen to stumble across one, and decide to spend up to ~C~ yen in exchange for some of its tasty drinks. There are ~N~ vending slots in the vending machine, each with two types of drinks. For slot ~i~, the first type of drink costs ~a_i~ yen and has a tastiness value of ~b_i~, whereas the second type of drink costs ~c_i~ yen and has a tastiness value of ~d_i~. To ensure equal sales of drinks in the same slot, for any given slot, the machine will only offer the type of drink you purchased less of, offering both drinks if you've purchased the same amount of each type. Note that the drinks offered are independent for each slot. For example, if there are two slots and you purchased more type ~1~ drinks from slot ~1~ but the same amount of type ~1~ and type ~2~ drinks from slot ~2~, slot ~1~ will only offer the type ~2~ drink while slot ~2~ still offers both types. As a lover of tasty drinks, please find the maximum possible sum of tastiness values you can get by spending up to ~C~ yen on the drinks.
~1 \le N \le 100~
~1 \le C, a_i, c_i \le 10^5~
~1 \le b_i, d_i \le 10^9~
Subtask 1 [10%]
~N = 1~
Subtask 2 [15%]
For all ~i~, ~a_i = c_i~ and ~b_i = d_i~.
Subtask 3 [15%]
~1 \le C < 10^5~
For all ~i~, ~c_i = 10^5~.
Subtask 4 [60%]
No additional constraints.
The first line contains ~2~ integers ~N~ and ~C~.
The next ~N~ lines each contain ~4~ integers ~a_i, b_i, c_i,~ and ~d_i~.
Output one integer, the maximum possible sum of tastiness values you can get by spending up to ~C~ yen on the drinks.
Sample Input 1
1 1000 300 4 400 9
Sample Output 1
Explanation for Sample 1
One possible plan is to purchase the second type of drink first, having a tastiness value of ~9~ and leaving you with ~600~ yen. Then, the machine only allows you to purchase the first type of drink since you bought less of it. After purchasing the first type of drink, the total tastiness value is ~13~ and you have ~300~ yen left. Both drinks are available once again, but you can only afford one more of the first type, leaving you with a total tastiness value of ~17~ in the end.
This sample input satisfies the constraints of subtasks ~1~ and ~4~.
Sample Input 2
3 2000 123 5 123 5 213 9 213 9 321 12 321 12
Sample Output 2
Explanation for Sample 2
The best decision is for you to get ~4~ drinks from the first slot and ~7~ drinks from the second (it doesn't matter which type of drink you purchase from each slot since they have the same costs and tastiness values). This gives a total tastiness value of ~4 \times 5 + 7 \times 9 = 83~.
This sample input satisfies the constraints of subtasks ~2~ and ~4~.
Sample Input 3
4 1500 314 15 100000 29358203 926 53 100000 1249284 589 79 100000 22667121 323 84 100000 47458321
Sample Output 3
Explanation for Sample 3
To maximize the sum of tastiness values, you should get one drink of the first type from each of slots ~1, 3,~ and ~4~. This gives a total tastiness value of ~15 + 79 + 84 = 178~.
This sample input satisfies the constraints of subtasks ~3~ and ~4~.
Sample Input 4
5 100000 271 828182845 904 523536028 747 135266249 775 724709369 995 957496696 762 772407663 353 547594571 382 178525166 427 427466391 932 305992181
Sample Output 4
Explanation for Sample 4
It is important to note that the answer may not fit in a ~32~-bit data type.
This sample input satisfies the constraints of subtask ~4~.