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 pi 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ă p1, p2, ..., pm, 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 <= pi <= 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.