Fişierul intrare/ieşire:	secv2m.in, secv2m.out	Sursă	Algoritmiada 2009, Runda Finala
Autor	Cosmin Gheorghe	Adăugată de	Gheorghe Cosmin •gcosmin
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Secv2m

Ingrid are iar de rezolvat o problema cu secvente. Ea are doua siruri de numere intregi de lungime N si respectiv M. Ea vrea sa gaseasca doua subsecvente de lungime L, una din primul sir si cealalta din al doilea sir, A_i1, A_i2, ... , A_iL si B_j1, B_j2, ... , B_jL astfel incat max(A_i1 + B_j1, A_i2 + B_j2, ..., A_iL + B_jL) sa fie minim posibil.

Date de intrare

Fişierul de intrare secv2m.in va contine pe prima linie numerele N, M si L. A doua linie contine N numere intregi reprezentand primul sir, iar a treia linie contine M numere intregi reprezentand al doilea sir.

Date de ieşire

În fişierul de ieşire secv2m.out veti afisa pe prima linie valoarea minima ceruta. A doua linie va contine pozitia de inceput a primei subsecvente si pozitia de inceput a celei de a doua subsecvente separate printr-un spatiu. Daca exista mai multe solutii se va alege cea in care prima subsecventa are cea mai mica pozitie de inceput. Daca si in acest caz exista mai multe solutii se va alege solutia in care a doua subsecventa are cea mai mica pozitie de inceput.

Restricţii si precizari

• 1 ≤ L ≤ N, M ≤ 2000
• Toate numerele din fisierul de intrare sunt cuprinse intre 0 si 10⁸

Exemplu

Explicaţie

Subsecventele alese sunt : 4 3 4 2 2 si 3 1 3 2 5 3 2 (Atentie, se cer subsecvente si nu subsiruri).

Cum se trimit solutii?