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.
Answer
asio wybrał się ze znajomymi na majówkę na Mazury. Ekipa podjęła decyzję żeby na wyprawę pojechać jego samochodem. Niestety, w trakcie podróży okazało się, że pogoda jest dość chłodna i Jasio rozważa teraz włączenie klimatyzacji aby podnieść temperaturę w pojeździe. Układ klimatyzacji jest dość niewygodny w obsłudze. Składa się z N nawiewów ustawionych obok siebie. i-ty z nich ma moc Mi, czyli zwiększa temperaturę w pojeździe o dokładnie Mi stopni Bajcjusza. Czasami moc nawiewu może być ujemna i wtedy zmniejsza on temperaturę w samochodzie. Na szczęście Jasio ma ze sobą dwie klapy. Dla~każdej z~nich może podjąć decyzję aby jej użyć lub nie. Użycie klapy polega na nałożeniu jej na wybrane przez siebie trzy kolejne nawiewy. Przykryte przez klapę nawiewy przestają zmieniać temperaturę. Klapy mogą się nakładać na~siebie, ale jeżeli już zostaną użyte, to muszą w całości przykryć jakieś trzy sąsiednie nawiewy (nie jest na przykład możliwe przykrycie tylko dwóch pierwszych nawiewów lub ich częściowe przykrywanie). Jasio zastanawia się o ile najwięcej stopni Bajcjusza jest w stanie podnieść temperaturę (jeżeli w ogóle opłaca mu się uruchomić klimatyzację). Wejście W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę nawiewów w samochodzie Jasia. W drugim wierszu wejścia znajduje się N liczb całkowitych Mi oznaczających moce kolejnych nawiewów w samochodzie Jasia. Wyjście W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca największą możliwą liczbę stopni Bajcjusza, o które może wzrosnąć temperatura w samochodzie Jasia. Ograniczenia 3 ≤ N ≤ 200 000, − 1 000 000 ≤ Mi ≤ 1 000 000. Przykład Input Output Explanation 6 -2 7 -1 -13 2 -7 5 Jasio może użyć obu klap przykrywając sumarycznie cztery nawiewy. Input Output Explanation 6 -3 0 1000 -3 -6 2 997 Wystarczy użyć jednej klapy do osiągnięcia optymalnego wyniku. Input Output Explanation 8 -1 -1 -1 -1 -1 -1 -1 -1 0 W tym przypadku nie warto włączać klimatyzacji. Input Output Explanation 3 2 0 23 25 Jasiowi opłaca się włączyć klimę i nie używać żadnej z klap.
Answer

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2024 KUDO.TIPS - All rights reserved.