And water can sustain us!
There are N days remaining until New Year, and everyone is gearing up for the celebrations. The local school, where Margarita Izoldovna teaches, is no exception. This year, she plans to organize numerous contests and decorate the hall. Given that the contests are quite tiring, participants will need to quench their thirst. Therefore, it has been decided to purchase K liters of water. With the hall not yet ready and time running short, she has enlisted the help of her best student, Izya, to buy the required amount of sweet water with the funds provided. Margarita Izoldovna is not concerned about whether Izya returns any change or how he transports the water; her main concern is that there is enough water.
As the holidays approach, shop owners have started behaving unpredictably, frequently changing prices. This means it might sometimes be advantageous to buy a bottle of water one day and sell it at full price the next. Izya quickly realized he could potentially make a profit from this situation.
Your task is to determine how much money Izya can earn, given that each day he can perform at most one of the following actions:
Buy one bottle of water;
Resell a bottle of water;
Return a bottle, keeping the water for himself.
Input
The first line contains three integers N, M, and K, where N is the number of days until the holiday, M is the amount of money given by the teacher (M ≤ 100,000,000), and K (K ≤ 250) is the amount of water Izya needs to buy.
The second line contains N natural numbers w_i ≤ 10,000, representing the cost of a bottle of water on the i-th day.
The third line contains N natural numbers c_i ≤ 10,000, representing the cost of an empty bottle on the i-th day.
Output
Output the maximum amount of money Izya can earn. If it is impossible for him to complete the teacher's task, output -1.