It's Halloween again, and Alice got a whole slew of candy for her many candy-dependent children. It's a lucky time for her too, because she was just running out of all of her Halloween candy, and she wants to ration her current stock to keep her children alive for as long as possible.

Each child has a metabolism level ~A_i~ and a hunger level ~B_i~. At the beginning of each day, their hunger level ~B_i~ will decrease by 1 and Alice can choose to feed exactly ~3~ children. Whenever she feeds a child, she will replenish them with calories, increasing their hunger level ~B_i~ by their metabolism level ~A_i~. If at the end of the day, any child has hunger level ~0~, then they die. Before the beginning of the first day, before their hunger level decreases, each child's satisfies ~B_i=A_i~.

Alice has ~N~ children, and she wants to keep them all alive for ~K~ full days (that means there are ~K~ day beginnings and ~K~ day ends!), but that may not be possible! So, can you tell her what the maximum number of babies she can keep alive for ~K~ full days is?

Constraints

For all subtasks:

~1\le A_i\le 2\times 10^5~

~1\le K\le 2\times 10^5~

Batch 1 [20%]

~1\le N\le 1000~

Batch 2 [80%]

~1\le N\le 10^5~

Input Specifications

The first line will contain two integers ~N~ and ~K~.

The next line will contain ~N~ integers, the ~i~-th of which corresponds to ~A_i~.

Output Specification

One line with one integer, the maximum number of babies that can be kept alive for ~K~ full days.

Sample Input

6 4
1 1 1 1 1 1

Sample Output

3

Sample Explanation

If you choose 3 children and feed them every day, then you can keep them alive indefinitely.

Sample Input

6 2
1 3 2 1 1 2

Sample Output

5

Sample Explanation

Take children 2 to 6. The values of ~A_i~ and ~B_i~ are outlined below:

~A_i~	3	2	1	1	2
~B_i~	3	2	1	1	2

On the first day, they each lose one hunger level. Feed the last three children to increase their hunger levels.

~A_i~	3	2	1	1	2
~B_i~	2	1	0	0	1
~B_i~	2	1	1	1	3

On the second day, they each lose one hunger level. Feed the middle three children to increase their hunger levels.

~A_i~	3	2	1	1	2
~B_i~	1	0	0	0	2
~B_i~	1	1	1	1	2

After the second day, they each have over ~0~ hunger levels, so it is possible to feed 5 children.

If, instead, she took all 6, then at the end of 2 days there would be at least one baby that doesn't have enough food.

~A_i~	1	3	2	1	1	2	Comments
~B_i~	1	3	2	1	1	2	Initial
~B_i~	0	2	1	0	0	1	Day 1: their hunger levels decrease by 1
~B_i~	1	2	1	1	1	1	Day 1: you must feed the children with 0 hunger levels so they end the day with a positive amount
~B_i~	0	2	0	0	0	0	Day 2: their hunger levels decrease by 1

No matter how you feed them, at the end of day two, at least one child will have a hunger level of ~0~.