3. Obojstranná čokotuba

Samo a Jano sú influenceri. Od čokofirmy dostali masívnu reklamnú obojstrannú tubu rôznofarebných čokoládiek pre dvojičky. Vraj aby sa odfotili, ako im chutí a aké skvelé to je, že sa nemusia hádať, kto si vytiahne čokoládu prvý. Každý vie, že rôzne farby čokoládiek znamenajú rôzne obsiahnuté živiny. Keďže Samo a Jano chcú všetkým ukázať, ako vyvážene sa stravujú, zrátali si, koľko ktorých čokoládiek chcú zjesť. Dve purpurové, šesť egyptských modrých, jedna nachová, tri indigové, sedem sivých…

Tuba s čokoládkami je otvorená z dvoch strán. Samo a Jano začali zbesilo vyťahovať čokošky z jednej strany. Keď nejakú vytiahnú, tak ju rovno aj zjedia, aj keď nepatrí do ich požiadaviek na vyváženú stravu. Keby ju nezjedli, určite by sa niekde stratila. To by bola škoda. Rýchlo si však uvedomili, že čím viac nechcených čokoládiek zjedia, tým horšiu mienku o nich budú mať ich sledovatelia.

Nuž, Samo začal hútať, koľko čokoládiek z ktorej strany to majú vlastne vybrať, aby sa najedli čo najmenej, ale aby zároveň uspokojili svoje potreby vyváženej stravy. Ak budú musieť tých zlých čokolád zjesť priveľa, nebudú ani chcieť pristúpiť na takúto ponuku sponzora. A podobných ponúk určite príde ešte veľa. Hodil by sa im preto program, ktorý pre danú tubu čokoládiek a ich potreby vyváženej stravy vypočíta, koľko najmenej čokoládiek budú musieť vytiahnúť, aby sa dostali k tým, čo chcú. Pomôžete im udržať priazeň publika?

Úloha

Tuba je priehľadná a otvorená z dvoch strán. Vnútri sú čokoládky naskladané v rade vedľa seba. Samo a Jano chcú vybrať z tuby aspoň \(a_1\) čokoládiek farby \(f_1\), aspoň \(a_2\) čokoládiek farby \(f_2\), …, aspoň \(a_m\) čokoládiek farby \(f_m\).

Vašou úlohou je zistiť, koľko najmenej čokoládiek musia dokopy z tuby vybrať tak, aby splnili svoje požiadavky. V každom momente môžu vybrať buď čokoládku úplne zľava, alebo čokoládku úplne sprava.

Formát vstupu

Na prvom riadku dostanete čísla \(n\) - počet všetkých čokoládiek v tube, \(m\) - počet Samových a Janových požiadaviek a \(f\) - počet rôznych farieb čokoládiek, ktoré sa môžu vyskytovať v tube. Platí, že \(1 \leq f \leq n \leq 500\,000\) a \(0 \leq m \leq f\).

Na druhom riadku je \(n\) čísiel \(c_1\) až \(c_n\) - farby čokoládiek tak, ako sú v tube zľava doprava. Farby majú čísla od \(1\) po \(f\). To však neznamená, že sa na vstupe musia nutne vyskytovať všetky farby od \(1\) po \(f\).

Nasleduje \(m\) riadkov. V \(i\)-tom z nich sú čísla \(a_i\) a \(f_i\). Tie znamenajú, že Samo a Jano chcú z tuby vybrať aspoň \(a_i\) čokoládiek farby \(f_i\). Môžete predpokladať, že všetky \(f_i\) sú navzájom rôzne a tiež, že pre zadanú tubu sú všetky požiadavky vždy splniteľné.

Formát výstupu

Na výstup vypíšte jedno číslo - koľko najmenej čokoládiek musia Samo s Janom z tuby vybrať, aby splnil všetky svoje požiadavky.

Príklady

Input:

6 2 3
1 2 2 1 3 2
1 1
3 2

Output:

4

Naši súrodenci chcú jednu čokoládu farby 1 a tri čokolády farby 2. Môžu teda zobrať napríklad 3 čokolády zľava a jednu sprava.

Input:

5 1 3
1 2 2 3 1
1 2

Output:

2

Teraz chcú iba jednu čokoládu farby 2. Tá ale nie je na kraji, tak sa k nej musia dostať cez najľavejšiu čokoládu farby 1.