In her chemistry class, Ms. Chong decides to troll her students. She injects some low-concentrated bases into the pH indicator so that it appears purple. However, once the liquid is mixed with the acidic lemon juice, the indicator will turn colourless. Ignorant of this fact, Ms. Chong's students look forward to seeing purple lemons. You, as the only student in the class who sees through Ms. Chong's trick, want to troll your teacher back. You decide to make Ms. Chong over-inject the number of bases to turn the lemon purple. You prepared an infinite amount of different types of bases for Ms. Chong. The base with type has a volume of mL and a base value of . Each minute, Ms. Chong is going to add up to mL of bases into the lemon. The base value of the lemon at the minute is the sum of the base value of all the bases that Ms. Chong added in the first minutes. Determine the maximum base value that Ms. Chong can add to the lemon in minutes.
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
Input Specification
The first line will contain two space-separated integers, and .
The second line will contain space-separated integers, , respectively.
The next lines will contain two space-separated integers, and .
Output Specification
Output the maximum amount of base Ms. Chong can add to a lemon in minutes.
Sample Input
3 3
2 3 5
3 3
4 5
5 8
Sample Output
11
Comments