ksecv4

Ksecv4

h2. 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$.

Pe prima linie a fişierului $ksecv4.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$.

h2. 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$.

Pe prima linie a fişierului de ieşire $ksecv4.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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1 000 000$
* $1 ≤ K ≤ 1 000$
* $1 ≤ M ≤ 2 048$

13 4 6 19 4 10
0 0 0 0 0 0
| 5

|

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

|

| 6 3 3
3 4 2
4 5 3