Problem C
Ankamyderna

Kalle har precis fått en stor låda med färgglada gummiankor som present. Efter att ha räknat dem noggrant vet han exakt hur många ankor han har av varje färg. Nu vill han bygga världens största ankpyramid!

För att bygga pyramiden har Kalle fått låna ett speciellt pyramidsbyggnadsställ, vars höjd max tillåter en att bygga en pyramid med upp till $M$ lager av ankor. En ankpyramid byggs i lager, där det nedersta lagret är lager 1, nästa är lager 2, och så vidare. För att pyramiden ska se bra ut har Kalle bestämt att varje lager ska bestå av ankor av samma färg. Han har också bestämt vilken färg varje lager ska ha.

Om pyramiden har höjd $H$, så måste lager $i$ innehålla exakt $(H-i+1)^2$ ankor. Till exempel, i en pyramid med höjd 3:

• Lager 1 (nederst) behöver $3^2 = 9$ ankor.

• Lager 2 (mitten) behöver $2^2 = 4$ ankor.

• Lager 3 (överst) behöver $1^2 = 1$ anka.

Figure 1: Harrys reaktion när han ser en ankamyd där lager 1 består av $9$ gula ankor, lager 2 består av $4$ blåa ankor, och lager 3 består av $1$ grön anka.

Hjälp Kalle att räkna ut hur hög pyramiden kan bli! Notera att höjden $H$ inte kan överstiga $M$.

Indata

På första raden finns två heltal $N$ och $M$ ($1 \le N, M \le 10^5$), antalet olika färger och antalet lager i pyramiden.

På andra raden finns $N$ heltal $a_1, a_2, ..., a_N$ ($0 \le a_j \le 10^{18}$), där $a_j$ anger antalet ankor av färg $j$.

På tredje raden finns $M$ heltal $c_1, c_2, ..., c_M$ ($1 \le c_i \le N$), där $c_i$ anger vilken färg som ska användas i lager $i$.

Notera att även om Kalle har bestämt vilka färger som alla lager ska ha, så bygger han kanske en pyramid som inte använder alla $M$ lager.

Utdata

Skriv ut ett heltal: den maximala höjden $H$ som pyramiden kan ha.

Poängsättning

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

Förklaring av exempelfall

I det första exemplet har Kalle bara ankor av en färg, och han har 17 stycken av dem. Pyramidstället tillåter upp till 5 lager. För att bygga en pyramid med höjd 3 behövs:

• 9 ankor i lager 1

• 4 ankor i lager 2

• 1 anka i lager 3

Totalt används 14 ankor. Det går inte att bygga en pyramid med höjd 4, eftersom det skulle kräva $4^2 + 3^2 + 2^2 + 1^2 = 30$ ankor, vilket är mer än de 17 ankor som finns tillgängliga.

I det andra exemplet har Kalle:

• 2 ankor av färg 1

• 19 ankor av färg 2

• 12 ankor av färg 3

Färgordningen i lagren är: 2, 3, 2, 1, 2. En pyramid med höjd 3 kan byggas genom att använda:

• 9 ankor av färg 2 i lager 1

• 4 ankor av färg 3 i lager 2

• 1 anka av färg 2 i lager 3

Detta använder 10 ankor av färg 2 och 4 ankor av färg 3, vilket är inom gränserna för vad som finns tillgängligt. En högre pyramid är inte möjlig med de givna begränsningarna.

1 5
17
1 1 1 1 1

3

3 5
2 19 12
2 3 2 1 2

3

2 3
4 2
1 2 1

2