Antrenorul unei echipe de joc sportiv are la dispoziţie un lot format din n jucători, numerotaţi de la 1 la n. Antrenorul cunoaşte pentru fiecare sportiv din lot două lucruri: valoarea şi postul pe care joacă. Valoarea unui jucător este un număr natural, iar posturile sunt codificate prin numerele 1, 2, ..., m. O echipă poate să joace într-o competiţie, dacă pentru fiecare post i are câte p_i sportivi, 1<= i<=m.

Cerinţă

Se cere să se determine numărul de echipe de valoare maximă pe care le poate forma antrenorul, care pot să participe la competiţie.

Date de intrare

Fişierul de intrare echipa.in conţine pe prima linie n, numărul sportivi, şi m, numărul de posturi din echipă, separate între ele prin câte un spaţiu. Pe linia a doua se află p₁, p₂, ..., p_m, separate prin câte un spaţiu, iar pe următoarele n linii câte două numere naturale separate prin câte un spaţiu, valoarea şi respectiv postul fiecărui jucător în ordinea codificării.

Date de ieşire

Fişierul de ieşire echipa.out va conţine o singură linie pe care se va scrie numărul de echipe din cerinţă, modulo 2003.

Restricţii

• 1 <= n <= 2500
• 1 <= m <= 30
• 1 <= p_i <= 10, pentru i=1, 2, …, m
• Valoarea unui sportiv <= 30
• Valoarea unei echipe este egala cu suma valorilor sportivilor.
• Două echipe sunt diferite dacă există un sportiv care se găseşte într-o echipă şi nu se găseşte în cealaltă.

Exemple

echipa.in	echipa.out	Explicaţie
8 3 2 2 1 10 2 5 3 20 2 20 1 10 2 10 3 22 3 30 1	2	Pe postul 1 avem sportivii: 4 şi 8 (cu valorile 20, respectiv 30). Pe postul 2 avem sportivii: 1, 3 şi 5 (cu valorile 10, 20, respectiv 10). Pe postul 3 avem sportivii: 2, 6 şi 7 (cu valorile 5, 10, respectiv 22). Cele doua echipele posibile sunt: 4 8 1 3 7 4 8 3 5 7 Valoarea acestor echipe este 20+30+20+10+22= 102.

prof. Doru Popescu Anastasiu

C.N. "Radu Greceanu", Slatina

dopopan@yahoo.com