There are N types of boxes, each with a given size that is a positive integer; the greatest size is H, and the sizes are distinct. The function A(n) is defined to be the least number of those boxes to hold n units of stuff without any leftover space; that is, their sizes have to add up to n. (Each type can be used any number of times. A(n) is undefined if this is impossible.)
If n is an element of a set S, n is called "relatively easy to make among S" if and only if A(n) is defined and there do not exist a and b in S such that a < n < b, A(a) and A(b) are defined, and A(n) ≥ ((b-n)A(a)+(n-a)A(b))/(b-a).
For a given positive integer ≤ T, find the greatest number that is relatively easy to make among the set of nonnegative numbers of the form kH+T, possibly up to a certain limit, where k is an integer. If present, the limit is greater than T.
Here's a hint: A related problem was discussed earlier in this training. The corresponding slides are attached. This may be useful.
Input
The first line contains the two integers N and T in that order, followed by the aforementioned limit if there is one, or 0 if there is no limit. The second line contains the N box sizes in descending order.
Output
The output should contain a single integer, the answer as described in the third paragraph; if no such number exists, the output should be empty.
Subtasks
#1 (10 points):
N ≤ 8;
H < 32;
T < 64; the limit is present and less than 128.
#2 (15 points):
N ≤ 128; H < 2048; 4294967296 ≤
T < 2
56; the limit is not present.
#3 (15 points):
N ≤ 512; H < 32768; 4294967296 ≤
T < 2
56; the limit is not present.
#4 (60 points):
N ≤ 16; H < 8192;
T < 2
56; the limit is not present.
Sample Test Case
Input
3 9 20
6 2 1
Output
3
Explanation
The set under consideration contains 3, 9, and 15. A(3) = 2 (1 and 2), A(9) = 3 (1, 2, and 6), and A(15) = 4 (1, 2, 6, and 6). 9 is not relatively easy to make among this set because A(9) ≥ ((15-9)A(3)+(9-3)A(15))/(15-3), but 3 is.