Roll Cake

Interview

Time limit2sMemory limit512 MB

Summary

Given up to M cuts across cakes of length at most 1000, maximise how many length-10 pieces you can cut out of them.

Level: Medium4 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

Today is Jaehyun's birthday. N friends each gave Jaehyun one roll cake as a gift. The lengths of the roll cakes are A1, A2, ..., AN. Jaehyun only eats roll cakes of length 10. So Jaehyun wants to cut the roll cakes to make as many length-10 roll cakes as possible.

A roll cake can be cut by the following process.

Choose one roll cake to cut. Only a roll cake whose length is greater than 1 can be cut. Let x be the length of the chosen roll cake.
Choose a natural number y such that 0 < y < x.
Cut the roll cake into two roll cakes of lengths y and x - y.

Jaehyun can cut the roll cakes at most M times. Write a program that finds the maximum number of length-10 roll cakes Jaehyun can obtain.

Input

The first line gives the number of roll cakes N and the maximum number of cuts M. (1 ≤ N, M ≤ 1,000)

The second line gives the lengths of the roll cakes A1, A2, ..., AN. (1 ≤ Ai ≤ 1,000)

Output

Print the maximum number of length-10 roll cakes Jaehyun can obtain.

Examples5

Example 1
Input
```
3 1
10 10 10
```
Expected output
```
3
```
Example 2
Input
```
3 1
10 10 20
```
Expected output
```
4
```
Example 3
Input
```
3 3
20 20 20
```
Expected output
```
6
```
Example 4
Input
```
5 7
10 20 30 40 50
```
Expected output
```
11
```
Example 5
Input
```
5 8
34 45 56 12 23
```
Expected output
```
8
```