시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 5 5 55.556%

문제

오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만들려고 한다.

롤케이크는 다음과 같은 과정을 통해서 자를 수 있다.

  1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
  2. 0보다 크고, x보다 작은 자연수 y를 고른다.
  3. 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.

재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤케이크의 개수 N과 자를 수 있는 최대 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄에 롤케이크의 길이 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000)

출력

재현이가 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 출력한다.

예제 입력 1

3 1
10 10 10

예제 출력 1

3

예제 입력 2

3 1
10 10 20

예제 출력 2

4

예제 입력 3

3 3
20 20 20

예제 출력 3

6

예제 입력 4

5 7
10 20 30 40 50

예제 출력 4

11

예제 입력 5

5 8
34 45 56 12 23

예제 출력 5

8
W3sicHJvYmxlbV9pZCI6IjE2MjA2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjN2FjXHVkNjA0XHVjNzc0XHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2YyBOXHViYTg1XHVjNWQwXHVhYzhjIFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyAxXHVhYzFjXHVjNTI5IFx1YzEyMFx1YmIzY1x1Yjg1YyBcdWJjMWJcdWM1NThcdWIyZTQuIFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+LCAuLi4sIEE8c3ViPk48XC9zdWI+XHVjNzc0XHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIDEwXHVjNzc4IFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjljYyBcdWJhMzlcdWIyOTRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1Yzc5OFx1Yjc3Y1x1YzExYyBcdWFlMzhcdWM3NzRcdWFjMDAgMTBcdWM3NzggXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwJm5ic3A7XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4NjRcdWNmMDBcdWM3NzRcdWQwNmNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1Yzc5MFx1Yjk3YyBcdWI4NjRcdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHVkNTU4XHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjljYyBcdWM3OTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjZTBcdWI5NzggXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyB4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAsIHhcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCB5XHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1Yzc5OFx1Yjc3YyBcdWFlMzhcdWM3NzRcdWFjMDAgeSwgeC15XHVjNzc4IFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWI0NTAgXHVhYzFjXHViODVjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1Y2Q1Y1x1YjMwMCBNXHViYzg4IFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCAxMFx1Yzc3OCBcdWI4NjRcdWNmMDBcdWM3NzRcdWQwNmMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1Yzc5MFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ2OWZcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDEsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yjg2NFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWFlMzhcdWM3NzQgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+LCAuLi4sIEE8c3ViPk48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgMTBcdWM3NzggXHViODY0XHVjZjAwXHVjNzc0XHVkMDZjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE2MjA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUm9sbCBjYWtlIiwiZGVzY3JpcHRpb24iOiI8cD5JdCZyc3F1bztzIEphZWh5dW4mcnNxdW87cyBiaXJ0aGRheSB0b2RheS4gSmFlaHl1biBnb3QgTiByb2xsIGNha2VzIGZyb20gTiBmcmllbmRzLCBvbmUgZnJvbSBlYWNoIGZyaWVuZC4gRWFjaCByb2xsIGNha2UmcnNxdW87cyBsZW5ndGggaXMgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+LCAmaGVsbGlwOywgQTxzdWI+TjxcL3N1Yj4uIEphZWh5dW4gb25seSBlYXRzIHJvbGwgY2FrZXMgb2YgbGVuZ3RoIGV4YWN0bHkgMTAuIFRoZXJlZm9yZSwgaGUgd2FudHMgdG8gY3JlYXRlIGFzIG1hbnkgcm9sbCBjYWtlcyBvZiBsZW5ndGggMTAgYXMgcG9zc2libGUgYnkgY3V0dGluZyB0aG9zZSBOIHJvbGwgY2FrZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgcm9sbCBjYWtlIGNhbiBiZSBjdXQgaW50byBzbWFsbGVyIG9uZXMsIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHByb2NlZHVyZS48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5GaXJzdCwgcGljayBhIHJvbGwgY2FrZSB0byBiZSBjdXQgLS0gaXRzIGxlbmd0aCBtdXN0IGJlIGdyZWF0ZXIgdGhhbiAxLiBMZXQgeCBiZSB0aGUgbGVuZ3RoIG9mIHRoZSBjaG9zZW4gcm9sbCBjYWtlLjxcL2xpPlxyXG5cdDxsaT5UaGVuLCBwaWNrIGFuIGludGVnZXIgeSB0aGF0IGlzIGdyZWF0ZXIgdGhhbiAwIGFuZCBsZXNzIHRoYW4geC48XC9saT5cclxuXHQ8bGk+VGhlIHJvbGwgY2FrZSBpcyBjdXQgaW50byB0d28gc21hbGxlciBvbmVzIG9mIGxlbmd0aCB5IGFuZCB4LXksIHJlc3BlY3RpdmVseS48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5KYWVoeXVuIGNhbiBjdXQgcm9sbCBjYWtlcyBhdCBtb3N0IE0gdGltZXMuJm5ic3A7IENvbXB1dGUgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvbGwgY2FrZXMgb2YgbGVuZ3RoIDEwIHRoYXQgaGUgY2FuIGdldC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIE4sIHRoZSBudW1iZXIgb2Ygcm9sbCBjYWtlcywgYW5kIE0sIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjdXRzIEphZWh5dW4gY2FuIHBlcmZvcm0gdXNpbmcgdGhlIG1hY2hpbmUgKDEgJmxlOyBOLCBNICZsZTsgMSwwMDApLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TjxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwKSZuYnNwO3doZXJlIEE8c3ViPmk8XC9zdWI+IGRlc2NyaWJlcyB0aGUgbGVuZ3RoIG9mIGFuIGktdGggcm9sbCBjYWtlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWF4aW11bSBudW1iZXIgb2Ygcm9sbCBjYWtlcyBvZiBsZW5ndGggMTAgdGhhdCBKYWVoeXVuIGNhbiBtYWtlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==