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 ((Vmax – Vmin + 1) / 2), unde Vmax este valoarea maximă din subsecvență, iar Vmin 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.

Cerinţă

Sa se determine 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.

Date de intrare

Pe prima linie a fișierului ksecv1.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 ksecv1.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⁶⁰ - 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

ksecv1.in	ksecv1.out	Explicaţii
6 3 6 13 4 6 19 4 10 0 0 0 0 0 0	5	Valorile vectorului V sunt 13 4 6 19 4 10. Dacă împărțim șirul în subsecvențele [0,2] [3,3] [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.
6 4 6 13 4 6 19 4 10 0 0 0 0 0 0	3	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.
6 3 3 3 4 2 4 5 3	3	Valorile vectorului V sunt 7 0 6 6 1 7. Dacă împărțim în subsecvențele [0,0] [1,4] [5,5], obținem șmecheriile 0, 3 și 0.

autor: stud. Eugenie Daniel Posdărăscu

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com