In "Blackjack", a popular card game, the goal is to have cards which sum up to the largest number not exceeding . Mirko came up with his own version of this game.
In Mirko's game, cards have positive integers written on them. The player is given a set of cards and an integer . He must choose three cards from this set so that their sum comes as close as possible to
without exceeding it. This is not always easy since there can be a hundred cards in the given set.
Help Mirko by writing a program that finds the best possible outcome of the given game.
Input Specification
The first line of input contains an integer
, the number of cards, and
, the number that we must not exceed.
The following line contains numbers written on Mirko's cards: distinct space-separated positive integers less than
.
There will always exist some three cards whose sum is not greater than .
Output Specification
The first and only line of output should contain the largest possible sum we can obtain.
Sample Input 1
5 21
5 6 7 8 9
Sample Output 1
21
Sample Input 2
10 500
93 181 245 214 315 36 185 138 216 295
Sample Output 2
497
Comments