Crete is famous for the savage tribes living there. There are $M$ caves arranged in a circle on the island. These caves are numbered clockwise from $1, 2, \dots, M$. There are $N$ savages living on the island. Initially, they live in caves $C_1, C_2, \dots, C_N$ respectively. Every year, the $i$-th savage moves $P_i$ caves clockwise to settle down. Each savage $i$ has a lifespan $L_i$, which is the number of years they live. The four figures below describe the situation for the first four years on an island with 6 caves and three savages. The initial cave numbers for the three savages are 1, 2, and 3; the number of caves they move each year are 3, 7, and 2; and their lifespans are 4, 3, and 1, respectively.

Figure 1, Figure 2, Figure 3, Figure 4

Strangely, although there are many savages, no two savages are ever in the same cave during their lifetimes, which keeps the island peaceful and quiet. This amazes scientists. They want to know: what is the minimum number of caves required to maintain peace on the island?

Input

The first line contains an integer $N$ ($1 \le N \le 15$), the number of savages. Each of the next $N$ lines contains three integers $C_i, P_i, L_i$ ($1 \le C_i, P_i \le 100$, $0 \le L_i \le 10^6$), representing the initial cave number, the number of caves moved each year, and the lifespan of each savage, respectively.

Output

Output a single integer $M$, the minimum possible number of caves. The input data is guaranteed to have a solution, and $M$ will not exceed $10^6$.

Examples

Input 1

3
1 3 4
2 7 3
3 2 1

Output 1

6

Note

This example corresponds to the case described in the problem statement.