#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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 **k****H**+**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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 8 | 1s | 64MB | Minimum |

2 | 15 | 8 | 1s | 64MB | Minimum |

3 | 15 | 8 | 1s | 64MB | Minimum |

4 | 60 | 12 | 1s | 64MB | Minimum |

5 | 0 | 1 | 1s | 64MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o easy -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512