10141번 - Pakowanie 다국어

Nadszedł czas biwaku! Na biwak trzeba zabrać różne rzeczy, a potem je ze sobą nosić, zatem podjęcie decyzji, które przedmioty są naprawdę niezbędne do skutecznego biwakowania, jest bardzo ważne. Na szczęście nie na tym polega Twoje zadanie, bowiem przedmioty do zapakowania zostały już wybrane. Teraz pozostało tylko zapakować je w plecaki.

Do każdego plecaka można włożyć dowolnie wiele przedmiotów, o ile tylko ich łączna masa nie przekracza jego udźwigu. Przedmiotów nie można dzielić, więc może się okazać, że pojemność użytych plecaków nie zostanie w całości wykorzystana.

Problem w tym, że plecaków jeszcze nie ma i trzeba je kupić. W sklepie dostępne są różne modele plecaków. Każdy plecak charakteryzuje się ustalonym udźwigiem, cena wszystkich plecaków jest jednakowa. Twoim zadaniem jest kupić plecaki, które wystarczą do zapakowania wszystkich przedmiotów na biwak oraz wydać przy tym jak najmniej.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n ≤ 24, 1 ≤ m ≤ 100), określające liczbę przedmiotów do zapakowania oraz liczbę dostępnych plecaków. W drugim wierszu znajduje się ciąg n liczb całkowitych a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁸); liczba a_i określa masę i-tego przedmiotu. W trzecim wierszu znajduje się ciąg m liczb całkowitych c₁, c₂, ..., c_m (1 ≤ c_i ≤ 10⁸); liczba c_i określa udźwig i-tego plecaka.

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca minimalną liczbą plecaków wystarczających do zapakowania wszystkich przedmiotów. Jeżeli zapakowanie przedmiotów nie jest możliwe, należy zamiast tego wypisać na wyjście jedno słowo NIE.

Można na przykład zakupić pierwszy i trzeci plecak. Najcięższy przedmiot może się wówczas znaleźć w plecaku o pojemności 11, zaś do plecaka o pojemności 9 można włożyć pozostałe przedmioty.