- Time limit: 1.00 s
- Memory limit: 512 MB
You are playing a game that consists of levels. Each level has a monster. On levels , you can either kill or escape the monster. However, on level you must kill the final monster to win the game.
Killing a monster takes time where is the monster's strength and is your skill factor. After killing a monster, you get a new skill factor (lower skill factor is better). What is the minimum total time in which you can win the game?
Input
The first input line has two integers and : the number of levels and your initial skill factor.
The second line has integers : each monster's strength.
The third line has integers : your new skill factor after killing a monster.
Output
Print one integer: the minimum total time to win the game.
Constraints
Example
Input:
5 100 50 20 30 90 30 60 20 20 10 90
Output:
2600
Explanation: The best way to play is to kill the second and fifth monster.