Meble

Limit pamięci: 128 MB

Bajtazar zamierza urządzić swoje nowe mieszkanie. W tym celu udał się do jednego z pobliskich sklepów sieci BITKEA i zakupił meble typów, konkretnie sztuk mebla typu .

Złożenie pierwszego mebla typu (wraz z przestudiowaniem instrukcji w języku bajtoszwedzkim) zajmie mu minut. Składając kolejne meble, Bajtazar będzie nabierał wprawy - złożenie drugiego i każdego kolejnego mebla typu zajmie mu o minut krócej niż złożenie poprzedniego mebla tego typu.

Bajtazar zdecydował, że jeszcze dziś złoży pewną liczbę mebli. Dla każdej z wartości chciałby wiedzieć, w jakim najkrótszym czasie może złożyć pewne spośród zakupionych mebli.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i () oznaczające odpowiednio liczbę typów mebli i liczbę wartości . W -tym z kolejnych wierszy znajdują się trzy liczby całkowite (), stanowiące opis -tego typu zakupionych mebli. W -tym z kolejnych wierszy znajduje się liczba całkowita ().

W testach wartych punktów zachodzi warunek .

W testach wartych punktów zachodzi warunek .

W testach wartych punktów zachodzi co najmniej jeden z powyższych warunków.

Wyjście

Na wyjście należy wypisać wierszy; w -tym z nich powinna znaleźć się minimalna liczba minut potrzebna do złożenia mebli. Można założyć, że złożenie pewnych mebli będzie zawsze możliwe.

Przykład

Dla danych wejściowych:

3 6
20 3 6
25 20 2
19 1 19
1
2
3
4
5
6

poprawną odpowiedzią jest:

19
30
49
62
70
75

Autor zadania: Adam Karczmarz.