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 iz datoteke autobusi.in.) 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 u datoteku autobusi.out.) 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

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int maxL = 100010;
const int maxLog = 20;
const long long besk = (long long)1 << 62;

typedef struct { int pozicija, vrednost; } Polje;
bool comparePolja(Polje const& p1, Polje const& p2) {
    return (p1.vrednost < p2.vrednost);
}


int n, m, p;
int a[maxL], pret[maxL], sled[maxL];
long long t[maxL];
long long l[maxL][maxLog], d[maxL][maxLog];

Polje polja[maxL];
void sortirajPolja() {
    for (int i = 0; i < m; i++) {
        polja[i].pozicija = i;
        polja[i].vrednost = a[i];    
    }     
    sort(polja, polja + m, comparePolja);
}

void ucitajPodatke() {
    freopen("autobusi.in", "r", stdin);
    scanf("%d%d%d", &m, &n, &p);
    for (int i = 0; i < m; i++) 
        scanf("%d", &(a[i]));
    for (int i = 0; i < p; i++) 
        scanf("%d", &(l[i][0]));
    for (int i = 0; i < p; i++) 
        scanf("%d", &(d[i][0]));
}

void preracunaj(long long x[][maxLog]) {
    long long tmin = x[0][0] + 1;
    for (int k = 0; k < 2; k++)
         for (int i = p - 1; i >= 0; i--) {
             if (tmin < x[i][0]) 
                 x[i][0] = tmin;
             else tmin = x[i][0];
             tmin++;
         }
    for (int j = 1; j < maxLog; j++)
        for (int i = 0; i < p; i++)
            x[i][j] = x[i][j - 1] + x[(i + x[i][j - 1]) % p][j - 1];
}

void nadjiSusedne() {
    int poslednji[maxL];
    for (int i = 0; i <= n + 1; i++) 
        poslednji[i] = -1;
    for (int i = 0; i < m; i++) {
        pret[i] = poslednji[a[i] + 1];
        poslednji[a[i]] = i;    
    }     
    for (int i = 0; i <= n + 1; i++) 
        poslednji[i] = -1;
    for (int i = m - 1; i >= 0; i--) {
        sled[i] = poslednji[a[i] + 1];
        poslednji[a[i]] = i;    
    }     
}

long long fmin(long long a, long long b) {
    return (a < b) ? a : b;   
}

long long potrebno(long long x[][maxLog], long long startT, long long udaljenost) {
    int tmp = 0; long long ret = 0; startT %= p;
    while (udaljenost > 0) {
        if ((udaljenost & 1) != 0) {
            ret += x[startT][tmp];
            startT = (startT + x[startT][tmp]) % p;                
        }
        tmp++;
        udaljenost >>= 1;     
    }
    return ret;    
}

void resi() {
    preracunaj(l);
    preracunaj(d);    
    nadjiSusedne();
    
    sortirajPolja();
    for (int i = 0; i < m; i++) 
        t[i] = (a[i] == 1) ? 0 : besk;
    for (int j = 0; j < m; j++) {
        int i = polja[j].pozicija;
        if (pret[i] >= 0)
           t[pret[i]] = fmin(t[pret[i]], t[i] + potrebno(l, t[i], i - pret[i]));
        if (sled[i] >= 0)
           t[sled[i]] = fmin(t[sled[i]], t[i] + potrebno(d, t[i], sled[i] - i));
    }
}

void sacuvajResenje() {
    freopen("autobusi.out", "w", stdout);
    long long res = -1;
    for (int i = 0; i < m; i++)
        if (a[i] == n && (res == -1 || res > t[i]))
            res = t[i];
    printf("%lld\n", res);
}

int main() {
    ucitajPodatke();
    resi();
    sacuvajResenje();
    return 0;
}