Description

Original source: NOI 2002

The island of Crete is famous for its savage tribes. There are $M$ caves arranged in a circle on the island. These caves are numbered clockwise as $1,2,\cdots ,M$.

The island is inhabited by $N$ savages. Initially, they live in caves $C_1,C_2,\cdots ,C_N$ respectively. Every year, the $i$-th savage moves forward $P_i$ caves clockwise to settle down. Each savage $i$ has a lifespan $L_i$, which is the number of years they survive. The following four diagrams illustrate the first four years of an island with $6$ caves and three savages. The initial cave numbers of the three savages are $1,2,3$; the number of caves they move each year are $3,7,2$; and their lifespans are $4,3,1$ respectively.

Strangely, despite the large number of savages, no two savages ever occupy the same cave during their lifetimes, ensuring the island remains peaceful and tranquil. This has greatly intrigued the scientists. They want to know: what is the minimum number of caves required to maintain peace on the island?

Input Format

The first line contains an integer $N$, the number of savages;

The next $N$ lines each contain three integers $C_i, P_i, L_i$, representing the initial cave number, the number of caves moved each year, and the lifespan of each savage.

Output Format

Output a single integer $M$, the minimum possible number of caves. The input data guarantees a solution, and $M$ does not exceed $10^6$.

Sample 1

This sample corresponds to the example in the problem description.

3
1 3 4
2 7 3
3 2 1

6

Constraints & Hints

For all data, $1\le N\le 15,1\le C_i,P_i\le 100,0\le L_i\le 10^6$.