I Work All Day

Time limit1sMemory limit512 MB

Summary

Given a list of saw settings and a tree height T, pick the setting H that minimizes T mod H, breaking ties by first appearance.

Level: Easy2 of 10
Topics: Implementation, Brute force, Math
Solved: No attempts yet

Problem

Michael is a lumberjack, and a decent one. Automation is moving into the trade fast, so he has to keep up to stay competitive.

He built a machine called the Flannelmaster GTX. It swings an axe horizontally at a height you set, measured from the ground. Each swing cuts the tree cleanly in two: the log below the blade rolls away as lumber, and the rest of the tree drops back down onto the same spot.

Once what is left is shorter than the setting, the machine can no longer cut and stops. The odd-sized stump that remains is thrown away as waste, and every log of the same length as the setting is packaged and sold automatically.

The machine accepts a fixed list of settings. Given the height of the tree, find the setting that wastes the least wood.

Input

The first line contains the integer $N$ ( $2 \le N \le 10$ ), the number of settings.

The second line contains $N$ distinct integers $H_i$ ( $1 \le H_i \le 500$ ), the settings you can choose from.

The third line contains the integer $T$ ( $1 \le T \le 3000$ ), the height of the tree.

Output

Print the setting that wastes the least wood.

The waste of a setting $H$ is the length left over after cutting as many logs of length $H$ as possible, that is $T \bmod H$ . If several settings leave the same smallest waste, print the one that appears first on the second line.

Examples2

Example 1
Input
```
3
5 6 8
103
```
Expected output
```
6
```
Example 2
Input
```
4
7 3 5 13
1366
```
Expected output
```
7
```