Problem B
Fast Charging

Sandra has become completely addicted to playing the mobile game Subway Surfers and can’t stop playing it. Unfortunately, her phone has limited battery capacity - when fully charged, it has $10^8$ micropercent, and each minute of use drains $1$ micropercent. Since the phone becomes very hot when used while charging, Sandra alternates between charging and playing over $N$ time intervals. Initially, the battery is fully charged, and she plays for $a_0$ minutes. She then charges for $a_1$ minutes, plays again for $a_2$ minutes, and continues this pattern until $a_n$. To ensure her phone doesn’t risk shutting down, it is crucial that the battery never falls below $10^6$ micropercent.

For this routine to work, Sandra must have a suitable charger. There are $C$ different chargers available, each at a different price. A charger that costs $c$ kronor also charges at a rate of $c$ micropercent/minute. Can you help Sandra determine the minimum cost of the charger she needs to support her gaming habits?

Input

The first line contains two integers $N$ and $C$ ($3 \leq N \leq 10^5, 1 \leq C \leq 10^5$), the number of intervals Sandra will play/charge and the number of available chargers.

The second line contains $N$ integers $a_i$ ($0 \leq i < N, 1 \leq a_i \leq 10^8$), where $a_i$ is the number of minutes Sandra plays or charges during the interval at index $i$.

The third and final line contains $C$ integers $c_i$ ($0 \leq i < C, 1 \leq c_i \leq 10^8$), where $c_i$ is both the price of the charger at index $i$ and how many micropercent per minute it charges.

Output

Output a single integer, the price of the cheapest charger Sandra can use. If no charger is suitable, output $-1$.

Scoring

Your solution will be tested on several test case groups. To receive points for a group, you must pass all test cases in the group.

Explanation

In the first sample, two chargers are available. With the first charger, Sandra would play and use the battery down to $10^8-1000=99999000$, charges to $99999000+10 \cdot 10 = 99999100$, and then plays down to $99998100$ micropercent. With the second charger, Sandra first plays down to $10^8-1000=99999000$, then charges to full since $99999000+10 \cdot 100000 > 10^8$, and finally plays down again to $10^8-1000=99999000$ micropercent. Both chargers work, so Sandra picks the cheaper one.

In the second sample, there are two chargers, but regardless of choice, Sandra will have only $10^8-99990000=10000$ micropercent left after playing for the second time, making neither charger sufficient.

In the third sample, Sandra initially plays down to exactly $10^8-99000000=10^6$ micropercent, which she finds acceptable. She then charges for $100$ minutes and plays for $1000$, resulting in less than $10^6$ micropercent battery unless she has a charger charging at least $10$ micropercent per minute. Finally, she charges for one more minute.

3 2
1000 10 1000
10 100000

10

5 2
100 10 99990000 100 10
100 100000000

-1

4 3
99000000 100 1000 1
1 10 100

10