Dato je m gradova, poređanih u nizu, i svaki od njih je označen nekim brojem (i-ti grad je označen brojem a_i, 1 ≤ a_i ≤ n). Naš čovečuljak kreće iz nekog grada označenog brojem 1, zatim mora da ode do nekog grada označenog brojem 2, itd, da završi u nekom gradu označenom brojem n.

Iz svakog grada na svakih sat vremena kreću po dva autobusa, jedan vozi u susedni grad s leve strane a drugi u susedni grad sa desne strane (osim iz prvog i poslednjeg grada, gde postoji samo po jedan autobus). U svetu našeg čovečuljka dan traje p sati, i sati su numerisani od 0 do p - 1. Poznato je da svi autobusi koji u t sati kreću na levo voze l_t sati, a oni koji kreću na desno voze d_t sati.

Čovečuljak u svakom gradu može da izabere da krene nekim autobusom ili može da čeka u tom gradu proizvoljan broj sati. Potrebno je odrediti broj T, najmanji broj sati koji je potreban čovečuljku da napravi traženi obilazak (garantuje se da će rešenje postojati). Čovečuljak kreće u 0 sati iz proizvoljnog grada označenog brojem 1.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulaza se nalaze tri broja, m, n i p. U sledećem redu nalazi se m brojeva, to su vrednosti a_i, a u sledeća dva reda po p brojeva - u prvom od njih se nalaze vrednosti l_i a u drugom d_i.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom redu izlaza treba ispisati izračunati broj T.

Ograničenja

1 ≤ n, m, p ≤ 10⁵, 1 ≤ l_i, d_i ≤ p. U 30% test primera biće p = 1, a u 40% n, m, p ≤ 1.000, pri čemu ukupno 60% test primera zadovoljava bar jedan od ova dva uslova.

Primer 1.

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

7

Objašnjenje.

Imamo 6 gradova, dan se sastoji od 4 sata. Autobusi koji kreću u 0 sati na levo voze 1h a na desno 3h, oni koji kreću u jedan sat na levo voze 4h, a na desno 2h, itd. Rexenje je na slici (X označava grad u kome smo na početku odgovarajućeg sata, a strelica označava smer u kome se vozimo u toku tog sata).

Primer 2.

10 4 6
2 4 4 4 2 3 1 3 1 4
2 5 1 3 6 4
1 3 2 4 5 2

12