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.

Constraints

~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.

Input Specification

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 Specification

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

17

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

83

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

178

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

115347629139

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.