시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2691 1235 1032 46.071%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 써져있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져있는 숫자가 주어졌을 때, M을 넘지않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21
5 6 7 8 9

예제 출력 1

21
W3sicHJvYmxlbV9pZCI6IjI3OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI3OTlcdWM3YWQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2U3NFx1YzljMFx1YjE3OFx1YzVkMFx1YzExYyBcdWM4MWNcdWM3N2MgXHVjNzc4XHVhZTMwIFx1Yzc4OFx1YjI5NCBcdWFjOGNcdWM3ODQgXHViZTE0XHViNzk5XHVjN2FkXHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWMwYzFcdWIyZjlcdWQ3ODggXHVjMjdkXHViMmU0LiBcdWNlNzRcdWI0ZGNcdWM3NTggXHVkNTY5XHVjNzc0IDIxXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkNTVjXHViM2M0IFx1YjBiNFx1YzVkMFx1YzExYywgXHVjZTc0XHViNGRjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVkMDZjXHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YmUxNFx1Yjc5OVx1YzdhZFx1Yzc0MCBcdWNlNzRcdWM5YzBcdWIxNzhcdWI5YzhcdWIyZTQgXHViMmU0XHVjNTkxXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1YWQ2ZCBcdWNkNWNcdWFjZTBcdWM3NTggXHViZTE0XHViNzk5XHVjN2FkIFx1YWNlMFx1YzIxOCBcdWFlNDBcdWM4MTVcdWM3NzhcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YmUxNFx1Yjc5OVx1YzdhZCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzBjMVx1YWRmYywgXHVjYzNkXHVjNjAxXHVjNzc0XHVjNjQwIFx1YWM4Y1x1Yzc4NFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWU0MFx1YzgxNVx1Yzc3OCBcdWJjODRcdWM4M2NcdWM3NTggXHViZTE0XHViNzk5XHVjN2FkXHVjNWQwXHVjMTFjIFx1YWMwMSBcdWNlNzRcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWMzNjhcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1YjUxY1x1YjdlY1x1YjI5NCBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmNmNFx1Yzc3NFx1YjNjNFx1Yjg1ZCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjhcdWI3ZjAgXHVkNmM0XHVjNWQwIFx1YjUxY1x1YjdlY1x1YjI5NCBcdWMyMmJcdWM3OTAgTVx1Yzc0NCBcdWQwNmNcdWFjOGMgXHVjNjc4XHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YzgxY1x1ZDU1Y1x1YjQxYyBcdWMyZGNcdWFjMDQgXHVjNTQ4XHVjNWQwIE5cdWM3YTVcdWM3NTggXHVjZTc0XHViNGRjIFx1YzkxMVx1YzVkMFx1YzExYyAzXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjZThcdWI3N2NcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJlMTRcdWI3OTlcdWM3YWQgXHViY2MwXHVkNjE1IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWFjZTBcdWI5NzggXHVjZTc0XHViNGRjXHVjNzU4IFx1ZDU2OVx1Yzc0MCBNXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgTVx1YWNmYyZuYnNwO1x1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFjMDBcdWFlNWRcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YzdhNVx1Yzc1OCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjMzY4XHVjODM4XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNXHVjNzQ0IFx1YjExOFx1YzljMFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBNXHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjZTc0XHViNGRjIDNcdWM3YTVcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMTggTigzICZsZTsmbmJzcDtOICZsZTsmbmJzcDsxMDApXHVhY2ZjIE0oMTAgJmxlOyZuYnNwO00gJmxlOyZuYnNwOzMwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTY5XHVjNzc0IE1cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWNlNzRcdWI0ZGMgM1x1YzdhNVx1Yzc0NCBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE1cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBNXHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjZTc0XHViNGRjIDNcdWM3YTVcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSkFDSyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gJmxkcXVvO0JsYWNramFjayZyZHF1bzssIGEgcG9wdWxhciBjYXJkIGdhbWUsIHRoZSBnb2FsIGlzIHRvIGhhdmUgY2FyZHMgd2hpY2ggc3VtIHVwIHRvIGxhcmdlc3QgbnVtYmVyIG5vdCBleGNlZWRpbmcgMjEuIE1pcmtvIGNhbWUgdXAgd2l0aCBoaXMgb3duIHZlcnNpb24gb2YgdGhpcyBnYW1lLjxcL3A+XHJcblxyXG48cD5JbiBNaXJrb1x1MjAxZnMgZ2FtZSwgY2FyZHMgaGF2ZSBwb3NpdGl2ZSBpbnRlZ2VycyB3cml0dGVuIG9uIHRoZW0uIFRoZSBwbGF5ZXIgaXMgZ2l2ZW4gYSBzZXQgb2YgY2FyZHMgYW5kIGFuIGludGVnZXIgTS4gSGUgbXVzdCBjaG9vc2UgdGhyZWUgY2FyZHMgZnJvbSB0aGlzIHNldCBzbyB0aGF0IHRoZWlyIHN1bSBjb21lcyBhcyBjbG9zZSBhcyBwb3NzaWJsZSB0byBNIHdpdGhvdXQgZXhjZWVkaW5nIGl0LiBUaGlzIGlzIG5vdCBhbHdheXMgZWFzeSBzaW5jZSB0aGVyZSBjYW4gYmUgYSBodW5kcmVkIG9mIGNhcmRzIGluIHRoZSBnaXZlbiBzZXQuPFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gYnkgd3JpdGluZyBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgYmVzdCBwb3NzaWJsZSBvdXRjb21lIG9mIGdpdmVuIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDMgJmxlOyBOICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBjYXJkcywgYW5kIE0gKDEwICZsZTsgTSAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIHRoYXQgd2UgbXVzdCBub3QgZXhjZWVkLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgbnVtYmVycyB3cml0dGVuIG9uIE1pcmtvXHUyMDFmcyBjYXJkczogTiBkaXN0aW5jdCBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIDEwMCAwMDAuPFwvcD5cclxuXHJcbjxwPlRoZXJlIHdpbGwgYWx3YXlzIGV4aXN0IHNvbWUgdGhyZWUgY2FyZHMgd2hvc2Ugc3VtIGlzIG5vdCBncmVhdGVyIHRoYW4gTS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGxhcmdlc3QgcG9zc2libGUgc3VtIHdlIGNhbiBvYnRhaW4uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 1번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: bupjae
  • 문제의 오타를 찾은 사람: joonas