Contest problemset description

Pan Wiesio znany jest z tego, że ,,robi u siebie jak u siebie’’, dlatego przed następnym remontem chciałby dowiedzieć się, ile uda mu się na nim zaoszczędzić, wykonując go samemu. Remont polega na położeniu dokładnie M metrów kwadratowych płytek, oczywiście bez krzyżaczków. Na Grochowie dostępnych jest N majstrów, i-ty z nich ma cennik składający się z trzech liczb:

• D_i – opłata początkowa,
• C_i – koszt położenia jednego metra kwadratowego płytek,
• Z_i – limit powyżej którego majster nie jest w stanie już pracować, tzn. może on położyć co najwyżej Z_i metrów kwadratowych płytek.

Twoim zadaniem jest obliczenie jaką kwotę zaoszczędzi pan Wiesio, czyli ile wyniósłby minimalny koszt wykonania remontu. Możesz założyć, że dane są dobrane tak, że wykonanie remontu jest zawsze możliwe.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M, będące odpowiednio liczbą majstrów oraz powierzchnią konieczną do wyremontowania. W kolejnych N wierszach znajduje się opis cenników majstrów. Każdy cennik składa się z trzech liczb całkowitych: D_i, C_i oraz Z_i, tak jak opisano w treści zadania.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca minimalnym kosztem wykonania remontu.

Ograniczenia

1 ≤ N, M ≤ 4000, 1 ≤ D_i, C_i ≤ 10⁷, 1 ≤ Z_i ≤ M.

Przykład

5 20
5 2 5
1 4 4
3 2 5
9 1 4
2 4 5

68

Alicja i Bogdan grają w grę Lewy Nim. Początkowo w grze znajduje się N stosów kamyczków, podobnie jak w grze Nim. Różnica jest taka, że ruch polega na zabraniu dodatniej liczby kamyczków, ze stosika znajdującego się najbardziej z lewej. Gracze wykonują ruchy naprzemiennie, zaczyna Alicja, a ten, kto nie może wykonać ruchu, przegrywa.

Twoim zadaniem jest wyznaczenie zwycięzcy tej gry, zakładając, że obaj gracze grają optymalnie.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita N, będąca początkową liczbą stosów kamyczków. W drugim wierszu wejścia znajduje się ciąg A₁, A₂, …, A_N, będący liczbami kamyczków na kolejnych stosikach, w kolejności od lewej.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno znaleźć się imię zwycięzcy gry.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ A_i ≤ 10⁹.

W testach wartych łącznie 20% maksymalnej punktacji zachodzi: N, A_i ≤ 5.

W testach wartych łącznie 60% maksymalnej punktacji zachodzi: N ≤ 1000.

Przykład

2
3 4

Alicja

3
1 5 2

Bogdan

4
2 1 2 1

Alicja

Pewnie umiesz już rozwiązywać proste nierówności, dlatego dzisiaj wyzwanie będzie nieco trudniejsze.

Twoim zadaniem jest policzenie liczby takich par dodatnich liczb całkowitych (x,y), dla których spełniona jest nierówność: x ⋅ y ⋅ (x+y) ≤ N.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się dodatnia liczba całkowita N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca liczbą par spełniających nierówność.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

W testach wartych łącznie 20% maksymalnej punktacji zachodzi: N ≤ 1000.

W testach wartych łącznie 50% maksymalnej punktacji zachodzi: N ≤ 1 000 000.

Przykład

17

6

100

29