Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info

Problem description


Halny
(halny)
Limit pamięci: 128 MB
Limit czasu: 1.50 s

Jedną z największych atrakcji turystycznych w Górach Badziewnych jest Rząd Drzew na Nudnawej Polanie, u podnóża Niepozornego Szczytu. Jak się można domyślić, jest to po prostu N drzew zasadzonych obok siebie w rzędzie.

Rząd Drzew jest dumą całego regionu, lecz z roku na rok staje się on coraz mniej okazały. Wszystko to za sprawą silnych wiatrów. Co roku, mniej więcej w okolicach października, zrywa się silny halny. Wieje on z Niepozornego Szczytu w kierunku Rzędu Drzew, zawsze od zachodu i powala niektóre drzewa. To, które dokładnie, zależy od wytrzymałości i wysokości drzew. Nieprzewrócone drzewo o wysokości h osłania drzewa posadzone na wschód od niego, które mają wysokość h lub mniejszą. Drzewa są zasadzone na tyle daleko od siebie, że powalone drzewo nie przewraca żadnych innych drzew, może ono jednak odsłonić inne drzewa, narażając je na działanie wiatru.

Instytut Meteorologii w Przekopanem przyjrzał się bliżej zjawisku corocznego halnego na Nudnawej Polanie. Profesor Andrzej Bachleda–Korpiel–Śliwka–Gąsienica–Bułecka opracował skomplikowany model, dzięki któremu może dokładnie przewidzieć siłę corocznych wiatrów. Siła wiatru jest charakteryzowana przez jedną liczbę – największą wytrzymałość powalanego przez ten wiatr drzewa.

Mając informacje o wytrzymałości i wysokości wszystkich drzew, a także prognozy siły wiatru w kolejnych latach, oblicz ile drzew zostanie powalonych po każdym roku.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone odstępem – oznaczają one kolejno liczbę drzew na polanie oraz liczbę corocznych prognoz.

W kolejnych N wierszach znajduje się opis poszczególnych drzew na polanie, od zachodu na wschód. Opis drzewa składa się z dwóch liczb naturalnych Hi oraz Wi, oddzielonych odstępem. Oznaczają one wysokość oraz wytrzymałość drzewa.

W kolejnych M wierszach znajdują się prognozy dla kolejnych lat. Prognoza składa się z jednej liczby naturalnej Si, oznaczającej siłę wiatru. Dokładniej oznacza to, że wiatr powali wszystkie nieosłonięte drzewa o wytrzymałości Si lub mniejszej.

Wyjście

Twój program powinien wypisać na wyjście M wierszy. W i-tym wierszu powinna się znaleźć liczba drzew powalonych przez halny w i-tym roku.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ M ≤ 300 000, 1 ≤ Hi, Wi, Si ≤ 109.

Przykład

Wejście Wyjście Wyjaśnienie
5 5
4 30
4 20
3 10
6 10
3 20
9
10
20
30
30
0
1
0
4
0

Wiatr w pierwszym roku jest za słaby, by powalić jakiekolwiek drzewo. Wiatr w drugim roku powala tylko najwyższe, czwarte drzewo. Nie powala on trzeciego drzewa, które jest osłaniane przez pierwsze i drugie drzewo. Wiatr w roku czwartym jest w końcu wystarczająco silny, aby powalić wszystkie pozostałe drzewa.