Problem B
Snabbladd

Sandra har blivit helt beroende av att spela mobilspelet Subway Surfers och kan inte sluta spela det. Dessvärre har hennes mobil begränsat med batteritid - när batteriet är fulladdat har det $10^8$ mikroprocent och varje minut av användande drar $1$ mikroprocent. Eftersom mobilen blir väldigt varm om man använder den samtidigt som man laddar får Sandra istället ladda och spela om vart annat under $N$ tidsintervall. Från början har mobilen fullt batteri och hon spelar i $a_0$ minuter. Sedan laddar hon i $a_1$ minuter. Efter det spelar hon igen, fast den här gången i $a_2$ minuter. Detta mönster fortsätter fram till $a_n$. För att mobilen inte ska riskera att dö är det väldigt viktigt för Sandra att mobilen aldrig har mindre än $10^6$ mikroprocent kvar i batteri.

För att det här ska kunna fungera måste hon såklart ha en bra laddare. Det finns $C$ olika laddare att köpa som kostar olika mycket. En laddare som kostar $c$ kronor laddar också $c$ mikroprocent/minut. Kan du hjälpa Sandra avgöra hur mycket den billigaste laddaren som fungerar med hennes spelvanor kostar?

Indata

Den första raden indata består av två heltal $N$ och $C$ ($3 \leq N \leq 10^5, 1 \leq C \leq 10^5$), antalet tidsintervall Sandra kommer spela/ladda och antalet laddare som finns att köpa. Den andra raden innehåller $N$ heltal $a_i$ ($0 \leq i < N, 1 \leq a_i \leq 10^8$), där $a_i$ är antalet minuter Sandra spelar eller laddar under intervallet med index $i$. Den tredje och sista raden innehåller $C$ heltal $c_i$ ($0 \leq i < C, 1 \leq c_i \leq 10^8$), där $c_i$ är hur mycket laddaren med index $i$ kostar samt hur många mikroprocent den laddar per minut.

Utdata

Skriv ut ett heltal, hur mycket den billigaste laddaren som Sandra kan använda kostar. Om det inte finns någon sådan ska du skriva ut $-1$.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I första sample finns två sladdar att välja på. Med den första skulle Sandra först spela till $10^8-1000=99999000$, sedan ladda till $99999000+10 \cdot 10 = 99999100$ och till sist spela till $99999100-1000=99998100$ mikroprocent. Med den andra sladden skulle Sandra först spela till $10^8-1000=99999000$, sedan ladda fullt eftersom $99999000+10 \cdot 100000 > 10^8$, och till sist spela till $10^8-1000=99999000$ mikroprocent igen. Eftersom båda sladdarna fungerar väljer Sandra den billigare av dem.

I andra sample finns det återigen två sladdar att välja på, men oavsett vilken hon väljer kommer hon bara ha $10^8-99990000=10000$ mikroprocent kvar efter andra gången hon spelar, alltså duger ingen av sladdarna.

I tredje sample börjar Sandra med att spela tills hon har $10^8-99000000=10^6$ mikroprocent kvar, vilket hon fortfarande tycker är okej. Sedan laddar hon i $100$ minuter och spelar i $1000$, vilket resulterar i mindre än $10^6$ mikroprocent batteri om hon inte har en laddsladd som laddar minst $10$ mikroprocent per minut. Till sist laddar hon i en minut till.

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