C. Calendar
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Davin is a very busy man, and he likes to get his schedule set on the day before a new year begins. The new year will be $$$2023$$$, and Davin has $$$N$$$ different events he needs to attend. He has those $$$N$$$ events represented by $$$A, B, C$$$, where $$$A$$$ and $$$B$$$ represent the month and day of the start date of the event, and $$$C$$$ represents how many days it takes to repeat that event. For example, if an event starts on August $$$6$$$th and repeats every $$$11$$$ days (August $$$6$$$, August $$$17$$$, August $$$28$$$, September $$$8$$$...), it would be represented by "$$$8$$$ $$$6$$$ $$$11$$$".

Davin would like to go on a vacation sometime during $$$2023$$$; thus, he wants to find the largest pocket of time where there are no events. Given the events Davin has during $$$2023$$$, output the largest pocket of time, in days, that he could go on a vacation.

Input

The first line will have $$$N$$$, where $$$N$$$ $$$1 \leq N \leq 100$$$ represents the number of events Davin has in $$$2023$$$.

The next $$$N$$$ lines will have $$$A, B, C$$$ $$$1 \leq C \leq 364$$$ where $$$A$$$ represents the month and $$$B$$$ represents the day of the date in which the event starts, and $$$C$$$ represents how many days between repeats of the event. It is guaranteed that $$$A$$$ and $$$B$$$ represent valid days in the calendar of the year $$$2023$$$.

Output

Find the biggest pocket of time, in days, in which Davin can go on a vacation.

Example
Input
3
3 27 4
6 24 2
8 6 11
Output
85
Note

After Davin marks all his events and when they will happen, the largest pocket of time he could go on vacation for is $$$85$$$ days, all the days before the first event of his year which starts on March $$$27$$$th.

$$$---------------------------------$$$

Idea: Spark

Preparation: Spark, Codicon + Bossologist

Occurrences: Novice 5, Intermediate 2