Darts

Interview

Time limit1sMemory limit256 MB

Summary

With up to four darts and N region scores, find the largest total not exceeding M, or 0 if every reachable total is over M.

Problem

You play a darts game with the following rules.

You may throw up to 4 arrows at the target. You do not have to throw all 4, and you may throw none at all.
The target is divided into $N$ regions, and region $i$ is labeled with a score $P_i$ . Several arrows may stick in the same region, and each one adds that region's score again.
Let $S$ be the total score of the regions where your arrows stick. This is the basis of your points.
For a predetermined value $M$ : if $S \le M$ , your score is exactly $S$ . However, if $S$ exceeds $M$ , your score becomes $0$ .

Given the scores written on the target and the value of $M$ , write a program that finds the maximum score you can obtain.

Read the following data from standard input.

The first line contains two integers $N$ and $M$ separated by a space. The target is divided into $N$ regions, and the predetermined value is $M$ .
Each of the next $N$ lines contains one integer; the $i$ -th of them ( $1 \le i \le N$ ) is $P_i$ , the score written on the $i$ -th region of the target.

Print the maximum score you can obtain on a single line.