Livrare

Două depozite ale unei hale țin mai multe pachete care trebuie livrate unor clienți. Pentru a face mai ușoară manevrarea pachetelor, angajații halei au așezat pachetele din fiecare depozit în ordine crescătoare, după greutate. Un curier trece pe la ambele depozite și colectează cât mai multe pachete pentru a reuși să le livreze în acea zi. Duba cu care urmează să transporte pachetele poate permite încărcarea a maxim $G$ kilograme. Curierul nu încarcă duba decât o singură dată pe zi, înainte de a pleca să livreze pachetele.

Cerințe

1. Considerând o echipă de $N$ curieri, fiecare cu propria dubă $i$ ce permite încărcarea a maxim $G_i$ kilograme, să se afișeze numărul de zile în care se pot trimite toate pachetele din depozit către destinatarii lor, dacă ordinea în care curierii preiau pachete din depozite este aceea a șirului de greutăți admise per dubă $G_i$ cunoscut. (50% din punctaj)

2. Într-o zi, un client sună să reclame că a primit alt pachet decât cel pe care îl aștepta. El comunică firmei de curierat greutatea pachetului pe care îl aștepta. În acest sens, echipa de $N$ curieri decide să caute în dubele lor pachetul clientului. În dube, pachetele sunt organizate după greutate, în mod crescător, așa cum au fost preluate de la depozit. Să se găsească în mod eficient duba $P$ în care se află pachetul clientului, indiferent de ziua în care se face reclamația. (50% din punctaj)

Date de intrare

Pe prima linie a fișierului de intrare livrare.in se găsește valoarea variabilei $c$, număr natural reprezentând cerința care va fi rezolvată.

Pe a doua linie, numerele naturale $A$ și $B$, reprezentând numerele de pachete din cele două depozite ale halei.

Pe următoarele două linii, șirurile de numere naturale reprezentând greutățile pachetelor din cele două depozite: $p_1, p_2, \dots, p_A$, respectiv $p_1, p_2, \dots, p_B$.

Pe a cincea linie, valoarea numărului natural $N$, reprezentând numărul de curieri.

Pe a șasea linie, șirul de numere naturale reprezentând greutățile admise ale dubelor: $G_1, G_2, \dots, G_N$.

Pentru cerința 2: Pe următoarea linie, greutatea $G_p$ a pachetului clientului.

Date de ieșire

În cazul în care prima cerință este cea rezolvată, în fișierul de ieșire livrare.out se va afișa un singur număr natural $Z$, reprezentând numărul de zile necesare pentru livrarea tuturor pachetelor din hală.

În cazul în care a doua cerință este cea rezolvată, în fișierul de ieșire livrare.out se va afișa un singur număr natural $P$, reprezentând a câta dubă este cea care conținea, de fapt, pachetul clientului.

Restricții

• $c \in \{1, 2\}$, reprezentând cerința dată spre rezolvare;
• $1 \leq A, B \leq 100$, cu $A$ și $B$ numere naturale, reprezentând numărul de pachete din fiecare depozit;
• $1 \leq p_i \leq 20$, unde $p_i$ este un număr natural reprezentând greutatea unui pachet dintr-un depozit, cu umrătoarele proprietăți:
  1. $p_1 \leq p_2 \leq \dots \leq p_i \leq \dots \leq p_A$, dacă $p_i \in$ depozitului $A$, respectiv $p_1 \leq p_2 \leq \dots \leq p_i \leq \dots \leq p_B$, dacă $p_i \in$ depozitului $B$;
  2. Toate greutățile $p_i$ din întreaga hală sunt distincte;
• $1 \leq N \leq 15$, unde $N$ este un număr natural reprezentând numărul de curieri;
• $1 \leq G_i \leq 1 \ 000$, unde $G_i$ este un număr natural reprezentând greutatea maximă admisă pentru duba $i$;
• $1 \leq G_p \leq 20$, unde $G_p$ este un număr natural reprezentând greutatea pachetului clientului;
• $1 \leq P \leq 15$, unde $P$ este un număr natural reprezentând a câta dubă cuprinde pachetul clientului.

Precizări

• Indiferent de zi, curierii ajung la hala în aceeași ordine, cea stabilită la citire;
• Pentru cerința 1: Se garantează că livrarea se poate face și, implicit, că nu există situații în care unele pachete să fie mai grele decât greutatea maximă admisă a oricărei dube;
• Pentru cerința 2: Nu se garantează că toate pachetele sunt distribuite în prima zi între curieri.

Exemplul 1

livrare.in

1
4 7
12 15 30 46
16 27 31 32 37 49 53
6
30 45 100 40 15 15 

livrare.out

3

Explicație

Dubele curierilor conțin în prima zi următoarele pachete descrise după valoarea $p_i$:

• Duba 1: $12, 15$
• Duba 2: $16, 27$
• Duba 3: $30, 31, 32$
• Duba 4: $37$
• Duba 5: goală
• Duba 6: goală

În a doua zi:

• Duba 1: goală
• Duba 2: goală
• Duba 3: $46, 49$
• Duba 4: goală
• Duba 5: goală
• Duba 6: goală

În a treia zi:

• Duba 1: goală
• Duba 2: goală
• Duba 3: $53$
• Duba 4: goală
• Duba 5: goală
• Duba 6: goală

Exemplul 2

livrare.in

2
4 7
12 15 30 46
16 27 31 32 37 49 53
6
30 45 100 40 15 15
49 

livrare.out

3

Explicație

În ziua a doua, pachetul cu greutatea $49$ a ajuns în a treia dubă.