시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2177 984 822 45.165%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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+Tlx1YzdhNVx1Yzc1OCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjMzY4XHVjODM4XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNXHVjNzQ0IFx1YjExOFx1YzljMFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBNXHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjZTc0XHViNGRjIDNcdWM3YTVcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMTggTigzICZsZTsmbmJzcDtOICZsZTsmbmJzcDsxMDApXHVhY2ZjIE0oMTAgJmxlOyZuYnNwO00gJmxlOyZuYnNwOzMwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjMzY4XHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NjlcdWM3NzQgTVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Y2U3NFx1YjRkYyAzXHVjN2E1XHVjNzQ0IFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTVx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0XHVjMTFjIE1cdWM1ZDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWNlNzRcdWI0ZGMgM1x1YzdhNVx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKQUNLIiwiZGVzY3JpcHRpb24iOiI8cD5JbiAmbGRxdW87QmxhY2tqYWNrJnJkcXVvOywgYSBwb3B1bGFyIGNhcmQgZ2FtZSwgdGhlIGdvYWwgaXMgdG8gaGF2ZSBjYXJkcyB3aGljaCBzdW0gdXAgdG8gbGFyZ2VzdCBudW1iZXIgbm90IGV4Y2VlZGluZyAyMS4gTWlya28gY2FtZSB1cCB3aXRoIGhpcyBvd24gdmVyc2lvbiBvZiB0aGlzIGdhbWUuPFwvcD5cclxuXHJcbjxwPkluIE1pcmtvXHUyMDFmcyBnYW1lLCBjYXJkcyBoYXZlIHBvc2l0aXZlIGludGVnZXJzIHdyaXR0ZW4gb24gdGhlbS4gVGhlIHBsYXllciBpcyBnaXZlbiBhIHNldCBvZiBjYXJkcyBhbmQgYW4gaW50ZWdlciBNLiBIZSBtdXN0IGNob29zZSB0aHJlZSBjYXJkcyBmcm9tIHRoaXMgc2V0IHNvIHRoYXQgdGhlaXIgc3VtIGNvbWVzIGFzIGNsb3NlIGFzIHBvc3NpYmxlIHRvIE0gd2l0aG91dCBleGNlZWRpbmcgaXQuIFRoaXMgaXMgbm90IGFsd2F5cyBlYXN5IHNpbmNlIHRoZXJlIGNhbiBiZSBhIGh1bmRyZWQgb2YgY2FyZHMgaW4gdGhlIGdpdmVuIHNldC48XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBieSB3cml0aW5nIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBiZXN0IHBvc3NpYmxlIG91dGNvbWUgb2YgZ2l2ZW4gZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMyAmbGU7IE4gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIGNhcmRzLCBhbmQgTSAoMTAgJmxlOyBNICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgdGhhdCB3ZSBtdXN0IG5vdCBleGNlZWQuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBudW1iZXJzIHdyaXR0ZW4gb24gTWlya29cdTIwMWZzIGNhcmRzOiBOIGRpc3RpbmN0IHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMTAwIDAwMC48XC9wPlxyXG5cclxuPHA+VGhlcmUgd2lsbCBhbHdheXMgZXhpc3Qgc29tZSB0aHJlZSBjYXJkcyB3aG9zZSBzdW0gaXMgbm90IGdyZWF0ZXIgdGhhbiBNLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdW0gd2UgY2FuIG9idGFpbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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