ksecv

Fie un vector V cu N elemente și un număr K. Vectorul V trebuie împărțit în exact K subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din $\displaystyle \left( \frac{V_{max} – V_{min} + 1}{2} \right)$, unde $V_{max}$ este valoarea maximă din subsecvență, iar $V_{min}$ este valoarea minimă.

Vectorul V de N elemente va fi generat în felul următor: se dă un număr M și 2 vectori A și B de lungime M (indexați de la 0 la M – 1). Fiecare element i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă: V[i] = (A[i % M] ^ B[i / M]), unde x % y reprezintă restul lui x la împărțirea cu y, x / y reprezintă câtul împărțirii lui x la y, și x ^ y reprezintă rezultatul operației xor (sau exclusiv pe biți) dintre x și y.

Date de intrare

Pe prima linie a fișierului ksecv.in se află 3 numere naturale N, K și M, cu semnificația din enunț, separate prin câte un spațiu. Pe a doua linie a fișierului se află M numere naturale separate prin câte un spațiu, reprezentând vectorul A. Pe a treia linie se află M numere naturale separate prin câte un spațiu, reprezentând vectorul B.

Date de ieșire

Pe prima linie a fișierului de ieșire ksecv.out se va afișa cel mai mic număr natural S pentru care vectorul V poate fi împărțit în exact K subsecvențe nevide, fiecare având șmecheria mai mică sau egală cu S.

Restricții

• 1 ≤ N ≤ 1 000 000
• 1 ≤ K ≤ 1 000
• 1 ≤ M ≤ 2 048
• N < M*M
• 1 ≤ K < N
• Valorile vectorilor A și B vor fi din intervalul $[0, 2^{60} - 1]$
• Fiecare din cele K subsecvențe trebuie să aibă cel puțin un element.
• Pentru 20% din teste N ≤ 100, K ≤ 50.
• Pentru alte 20% din teste N ≤ 100 000, K ≤ 1000.
• Pentru alte 20% din teste N ≤ 1 000 000, K ≤ 50.
• Vectorul V are indicii indexați de la 0 la N – 1.
• Vectorii A și B au indicii indexați de la 0 la M – 1.

Exemple

ksecv.in

6 3 6
13 4 6 19 4 10
0 0 0 0 0 0

ksecv.out

5

Explicaţii

Valorile vectorului V sunt 13, 4, 6, 19, 4, 10.
Dacă împărțim șirul în subsecvențele [0,2] [3,3] și [4,5] obținem șmecheriile 5, 0 și 3. Șmecheria maxima este 5.
Nu putem împărți vectorul V astfel încât șmecheria maximă a unei subsecvențe să fie mai mică decât 5.

ksecv.in

6 4 6
13 4 6 19 4 10
0 0 0 0 0 0

ksecv.out

3

Explicaţii

Valorile vectorului V sunt 13, 4, 6, 19, 4, 10.
O posibilă împărțire este: [0,0] [1,2], [3,3], [4,5]. Șmecheriile fiecărei subsecvențe sunt 0, 1, 0 și 3.

ksecv.in

6 3 3
3 4 2
4 5 3

ksecv.out

3

Explicaţii

Valorile vectorului V sunt 7, 0, 6, 6, 1, 7.
Dacă împărțim în subsecvențele [0,0], [1,4] și [5,5], obținem șmecheriile 0, 3 și 0.