시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

W bajtockim lesie rosną różne gatunki grzybków. Niedawno znany grzybiarz, Pan Stanisław, odkrył nowy, bardzo smaczny gatunek grzyba, który nazwał Staśkiem.

Staśki charakteryzują się tym, że można w łatwy sposób przewidzieć, o ile zwiększa się dziennie ich waga. Niestety, każdy grzyb po pewnej liczbie dni staje się grzybem trującym. Jednak dla Pana Stanisława nie jest to problem, ponieważ jako jeden z nielicznych, widząc dany grzyb, umie stwierdzić po ilu dniach będzie on niezdatny do spożycia.

Pan Stanisław wybrał się dzisiaj do bajtockiego lasu i spisał dane o wszystkich grzybach, które widział. Teraz zastanawia się, po ilu dniach ma wrócić do lasu, aby zebrać jak najwięcej (według wagi) grzybów. Pan Stanisław, mając do wyboru kilka terminów, zawsze wybiera najwcześniejszy. Żona Pana Stanisława zabrania mu chodzenia dwa razy do lasu jednego dnia, czyli Pan Stanisław nie może wrócić do lasu po 0 dniach.

입력

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 106), oznaczającą liczbę grzybów. W n następnych wierszach znajduje się opis kolejnych grzybów. Każdy wiersz zawiera trzy liczby całkowite m, p, d (1 ≤ m, p, d ≤ 105), oznaczające odpowiednio aktualną masę, przyrost wagi oraz ile dni dany grzyb jest zdatny do spożycia.

출력

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie dni, po których Pan Stanisław ma wrócić po grzyby.

예제 입력 1

3
1 1 2
5 5 3
7 2 4

예제 출력 1

2

힌트

  • po jednym dniu - masy grzybów to odpowiednio: (2, 10, 9),
  • po dwóch dniach - pierwszy grzyb jest niejadalny, masy grzybów: (0, 15, 11),
  • po trzech dniach- można jeść tylko trzeci grzyb, masy grzybów: (0, 0, 13),
  • po czterech dniach - żaden grzyb nie nadaje się do jedzenia: (0, 0, 0).

Jadalne grzyby najwięcej ważą 26 (po dwóch dniach).