Problem description

Ojciec Wirgilusz uczył dzieci swoje, a miał ich wszystkich 123456. Pewnego razu zabrał niektóre swoje dzieci, dokładnie N spośród nich, żeby kupić im buty na WF.

Na półce w sklepie znajduje się M par butów sportowych. Każda para ma przypisany rozmiar, oraz cenę (wyrażoną w Bitylingach). Każde dziecko musi mieć kupione buty w dokładnie takim samym rozmiarze jak rozmiar ich bieżących butów.

Wirgiliusz zastanawia się teraz, ile musi wziąć ze sobą pieniędzy do sklepu, żeby każde dziecko w sklepie mogło cieszyć się własną parą nowych butów. Może się okazać, że sklep nie ma wystarczającej liczby butów na stanie, wtedy Wirgiliusz będzie musiał poszukać innego sklepu.

Napisz program, który sprawdzi, czy możliwe jest kupienie butów dla dzieci w sklepie, a jeżeli tak, to jaki jest najmniejszy możliwy łączny koszt zakupów.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oznaczające odpowiednio liczbę dzieci w sklepie oraz liczbę par butów na sprzedaż.

W drugim wierszu wejścia znajduje się N liczb naturalnych s_i oznaczających rozmiary butów dzieci, które wybrały się z Wirgiluszem do sklepu.

W kolejnych M wierszach znajdują się opisy par butów na sprzedaż. W i-tym z nich umieszczono dwie liczby naturalne r_i i c_i, oznaczające odpowiednio rozmiar i cenę i-tej pary butów do sprzedania.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca minimalną liczbę bitylingów potrzebną do zakupu butów. Jeżeli nie da się kupić butów dla każdego, należy zamiast tego wypisać jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 123 456, 1 ≤ M ≤ 200 000, 20 ≤ s_i, r_i ≤ 50, 1 ≤ c_i ≤ 500.

Przykład

3 7
36 41 36
36 139
38 100
41 150
36 199
38 100
36 129
40 279

418

5 12
37 41 42 42 42 
36 199
37 199
37 199
40 219
41 219
41 219
41 219
41 219
41 219
41 219
42 219
42 219

NIE