Żarówki

Limit pamięci: 64 MB

Prace wykończeniowe w nowym domu Bajtazara dobiegają końca. Pozostało tylko wkręcić po jednej żarówce w każdym z pokoi. Dla każdego pokoju ustalił minimalną moc żarówki, która dostatecznie dobrze oświetli ten pokój.

Bajtazar kupił żarówek, lecz teraz zauważył, że nie spełniają one do końca jego oczekiwań. Być może nie jest możliwe dobre doświetlenie wszystkich pokoi, a być może niektóre żarówki niepotrzebnie mają tak dużą moc. Bajtazar postanowił więc wybrać się do sklepu i wymienić niektóre żarówki, tak aby móc wystarczająco oświetlić wszystkie pomieszczenia, a jednocześnie jak najbardziej ograniczyć łączną moc żarówek. Sklep dysponuje żarówkami o dowolnych dodatnich mocach. Plecak Bajtazar pozwala zabrać na wymianę co najwyżej żarówek - jest to maksymalna liczba żarówek, które gotów jest wymienić.

Pomóż Bajtazarowi wybrać, które żarówki należy wymienić na inne, tak aby wszystkie pokoje były wystarczająco oświetlone i jednocześnie by maksymalnie ograniczyć łączną moc żarówek.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (), oznaczające odpowiednio liczbę pokoi (jest to jednocześnie liczba żarówek) oraz liczbę żarówek, które można zmieścić w plecaku Bajtazara. Pokoje są ponumerowane od do . W drugim wierszu wejścia znajduje się liczb całkowitych () oznaczających moce żarówek, które aktualnie posiada Bajtazar. W trzecim wierszu wejścia znajduje się liczb całkowitych () oznaczających wymagania dotyczące oświetlenia w kolejnych pokojach - w pokoju należy wkręcić żarówkę o mocy co najmniej .

Wyjście

Jeśli nie da się tak wymienić co najwyżej żarówek, by wszystkie pokoje były dostatecznie oświetlone, na wyjście należy wypisać NIE. W przeciwnym wypadku należy wypisać jedną liczbę całkowitą, oznaczająca minimalną sumaryczną moc wszystkich żarówek użytych do oświetlenia domu po wymianie co najwyżej żarówek.

Przykład

Dla danych wejściowych:

6 2
12 1 7 5 2 10
1 4 11 4 7 5

poprawną odpowiedzią jest:

33

Wyjaśnienie do przykładu: Wystarczy wymienić żarówkę o mocy na żarówkę o mocy oraz żarówkę o mocy na żarówkę o mocy . Wówczas prawie wszystkie pokoje będą miały żarówki o dokładnie takiej mocy jak minimalne wymaganie. Wyjątkiem będzie pokój, który wystarczyłoby oświetlić żarówką o mocy , który zostanie oświetlony żarówką o mocy .

Autor zadania: Adam Karczmarz.