D. Clock Strikes Twelve
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob would like to buy a trading card pack today, but his local game store has some strange rules:

Firstly, they do not provide change, so he must come up with the exact amount of money to buy a trading card pack.

Secondly, they only accept $$$\textit{clean}$$$ coins, and unfortunately, all of Bob's coins are $$$\textit{dirty}$$$.

Thirdly, the $$$\textit{unluckiness}$$$ of the trading card pack you get is equal to the number of coins you pay with.

Finally, the store closes once midnight arrives.

Bob has an unlimited amount of $$$n$$$ types of dirty coins, each of which are worth $$$w_i$$$ cents and takes $$$t_i$$$ seconds to clean. Bob knows a trading card pack costs exactly $$$m$$$ cents, and midnight arrives in $$$k$$$ seconds. Bob needs to clean enough coins to buy a pack by the time midnight arrives, and minimize the unluckiness of his card pack. Find the minimum unluckiness of Bob's card pack if he spends his time wisely, or output $$$-1$$$ if Bob can not get a card pack!

Input

The first line of input will contain the integers $$$n$$$ $$$(1 \leq n \leq 500)$$$, $$$m$$$ $$$(n \leq m \leq 500)$$$, and $$$k$$$ $$$(1 \leq k \leq 500)$$$, the number of coin values, the cost of the card pack, and how soon midnight will arrive.

The second line of input will be the array $$$w$$$ $$$(1 \leq w_i \leq m)$$$, consisting of $$$n$$$ space-separated integers indicating the value of the $$$i^\text{th}$$$ coin.

The third line of input will be the array $$$t$$$ $$$(1 \leq t_i \leq 500)$$$, consisting of $$$n$$$ space-separated integers indicating the time it takes to clean the $$$i^\text{th}$$$ coin.

Output

Output the minimum unluckiness of a card pack that Bob can get, or $$$-1$$$ if he cannot clean enough coins in time to get a card pack.

Examples
Input
3 10 10
1 2 5
2 4 5
Output
2
Input
3 10 9
1 2 5
2 1 5
Output
4
Note

In the first test case, you should clean two of the 5-cent coins. You will finish just as midnight arrives.

In the second case, you should clean one 5-cent coin, two 2-cent coins, and one 1-cent coin.