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 si 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 ri i ci, 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 ≤ si, ri ≤ 50, 1 ≤ ci ≤ 500.
Przykład
Input Output Explanation
3 7
36 41 36
36 139
38 100
41 150
36 199
38 100
36 129
40 279
418
Można kupić dwie pary butów o rozmiarze 36 za 129 i 139 bitylingów oraz jedną parę w rozmiarze 41 za 150 buitylingów.
Input Output Explanation
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
Niestety, w tym przypadku nie jest możliwe zadowolenie wszystkich dzieci.
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 si 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 ri i ci, 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 ≤ si, ri ≤ 50, 1 ≤ ci ≤ 500.
Przykład
Input Output Explanation
3 7
36 41 36
36 139
38 100
41 150
36 199
38 100
36 129
40 279
418
Można kupić dwie pary butów o rozmiarze 36 za 129 i 139 bitylingów oraz jedną parę w rozmiarze 41 za 150 buitylingów.
Input Output Explanation
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
Niestety, w tym przypadku nie jest możliwe zadowolenie wszystkich dzieci.
Odpowiedź:
c++
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int N, M;
std::cin >> N >> M;
std::vector<int> shoe_sizes(N);
for (int i = 0; i < N; i++) {
std::cin >> shoe_sizes[i];
}
std::sort(shoe_sizes.begin(), shoe_sizes.end());
std::vector<std::pair<int, int>> shoes(M);
for (int i = 0; i < M; i++) {
std::cin >> shoes[i].first >> shoes[i].second;
}
std::sort(shoes.begin(), shoes.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
int total_cost = 0;
int i = 0;
for (int size : shoe_sizes) {
while (i < shoes.size() && shoes[i].first != size) {
i++;
}
if (i == shoes.size()) {
std::cout << "NIE" << std::endl;
return 0;
}
total_cost += shoes[i].second;
i++;
}
std::cout << total_cost << std::endl;
return 0;
}