After a successful Trick or Treat session, D1amond3x returns home to sort his candies. There are ~N~ types of candies in his candy pile. For the ~i^{\text{th}}~ candy type, he has ~T_i~ of those candies. He loves some candies more than others, but he is also a picky eater. For each candy type, he can choose exactly one of the following eating schedules:

• Eat one candy a day. He gains ~a_i~ happiness for the first candy, but for each following candy, the happiness gain decreases to ~a_i-1~, then ~a_i-2~, then so on until either the happiness gain reaches and remains at ~0~, or he runs out of candy.
• Eat one candy every two days. He gains ~b_i^2~ happiness for the first candy, but for each following candy, the happiness gain decreases to ~(b_i-1)^2~, then ~(b_i-2)^2~, then so on until either the happiness gain reaches and remains at ~0^2~, or he runs out of candy.
• Eat one candy every three days. He gains ~c_i^3~ happiness for the first candy, but for each following candy, the happiness gain decreases to ~(c_i-1)^3~, then ~(c_i-2)^3~, then so on until either the happiness gain reaches and remains at ~0^3~, or he runs out of candy.

Wanting to maximize happiness, he will select the schedule that gives him the most happiness. D1amond3x will only ever eat one type of candy at a time, and he will continue eating them until there are no more before beginning to eat the next candy type.

Unfortunately for him, he can only eat ~K~ types of candies before he gets bored of eating them, and throws out the rest.

What is the maximum amount of happiness he can obtain, and how many days will it take for him to reach that happiness? On the odd occasion that multiple eating schedules (including ones between different candies) result in the same happiness, he will choose the one that takes the least days to consume them all.

Since happiness may well exceed the 32-bit integer limit, you may need to use unsigned long long in C/C++, and a work-around solution in Java (ex: BigInteger). Note that only the last case will not pass with long.

Subtasks

~1 \leq N \leq 10^6~

~1 \leq T_i,a_i,b_i,c_i \leq 10^4~

~1 \leq K \leq N~

Subtask 1 [20%]

~1 \leq N \leq 10~

~1 \leq T_i,a_i,b_i,c_i \leq 10~

~K = 1~

Subtask 2 [30%]

~1 \leq N \leq 10^3~

~1 \leq T_i,a_i,b_i,c_i \leq 100~

Subtask 3 [50%]

No further constraints.

Input Specification

The first line will contain space-separated integers ~N,K~.

The next ~N~ lines will contain space-separated integers ~T_i,a_i,b_i,c_i~.

Output Specification

On the first line, output the maximum happiness D1amond3x can achieve.

On the second line, output the number of days it will take him to reach that happiness.

Sample Input 1

3 1
4 6 3 1
3 5 3 1
9 7 4 3

Sample Output 1

36
27

Explanation for Sample Output 1

For candy type ~1~, the happiness sums are as follows:

• Daily candy: he eats 4 candies, giving him a total happiness of ~6+5+4+3 = 18~.
• One candy every 2 days: he gains a total of ~3^2+2^2+1^2+0^2 = 9+4+1+0 = 14~.
• One candy every 3 days: he gains a total of ~1^3+0^3+0^3+0^3 = 1+0+0+0 = 1~.

Clearly, the optimal choice is to eat one candy a day for ~18~ happiness over 4 days.

Similarly for candy type ~2~, the happiness sums are ~12,14,1~, and for candy type ~3~, the happiness sums are ~28,30,36~, respectively.

For candy type ~2~, it is most optimal to eat one candy every 2 days, for ~14~ happiness over ~6~ days. For candy type ~3~, it is most optimal to eat one candy every 3 days, for ~36~ happiness over ~27~ days.

Since we can only pick one candy type to eat, it is best to eat candy type ~3~ for maximum happiness.

Sample Input 2

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

Sample Output 2

139
12