Runda 5: Bagaż podręczny

24.06.2009

Chciałbyś przewieźć pewne pakunki tramwajem. Niestety, za przewóz dużych pakunków trzeba zapłacić. Na szczęście na rynku działa wiele firm przewozowych, z których każda ma inne kryteria dotyczące rozmiaru paczek objętych opłatą. Oczywiście dla każdej firmy chciałbyś wiedzieć, za ile paczek będziesz musiał zapłacić, jeżeli wybierzesz jej usługi.

Wejście

W pierwszej linii wejścia dane są liczby n, m (1 ≤ n,m ≤ 1 000 000) oznaczające odpowiednio ilość paczek do przewiezienia oraz ilość firm transportowych. Następnie danych jest n linii, z których każda zawiera wysokość oraz szerokość jednej paczki (żaden z tych wymiarów nie przekarcza 5 000 000). Następnie danych jest m linii, z których każda opisuje minimalną wysokość oraz szerokość paczki, za przewóz której trzeba zapłacić w danej firmie. Każda firma wymaga opłaty za pakunek, jeżeli wysokość oraz szerokość paczki są jednocześnie niemniejsze od tych podanych w kryteriach.

Wyjście

Dla każdej firmy przewozowej należy wypisać, za ile paczek będzie trzeba zapłacić, jeżeli wybierze się jej usługi.

Przykład

Dla danych wejściowych

10 5
6 5
2 4
3 9
6 9
9 2
4 5
4 1
9 9
3 5
7 3
7 2
6 1
3 9
8 4
9 0

poprawną odpowiedzią jest

3
5
3
1
2

kod: LUGGAGE, limity: 8 s, 128 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com