National Olympiad in Informatics, China, 2002

The Crete islands are famously home to a society of savage cavemen. On the islands, there are ~M~ caves arranged in a loop shape. These caves are labeled ~1, 2, \dots, M~ in clockwise order. There are ~N~ cavemen living on the island, initially located in caves ~C_1, C_2, \dots, C_N~. Each year afterwards, the ~i~-th caveman will move clockwise by ~P_i~ caves. Each caveman has a lifespan of ~L_i~, the number of years they survive. The four figures below illustrate the scenario of an island with six caves and three cavemen, in the span of four years. The three cavemen initially live in the caves numbered ~1~, ~2~, and ~3~. Each year they move by ~3~, ~7~, and ~2~ caves, respectively. Their lifespans are ~4~, ~3~, and ~1~, respectively.

What's interesting is that although there are many cavemen, no two cavemen will ever share the same cave in any year of their lifetimes. This ensures that the little island will always maintain its peace and quiet, which is very puzzling for scientists. They would like to know, what is the minimum number of caves needed for the island to maintain its peace?

Input Specification

The first line of input contains a single integer ~N~ ~(1 \le N \le 15)~, the number of cavemen. Lines ~2~ to ~N+1~ each contain three integers ~C_i~, ~P_i~, and ~L_i~. ~(1 \le C_i, P_i \le 100~; ~0 \le L_i \le 10^6)~, representing the initial cave numbers of caveman ~i~, the number of caves it moves by per year, and its lifespan.

Output Specification

Output a single integer ~M~, the minimum number of caves required to maintain peace. There is guaranteed to be a solution, and ~M~ will not exceed ~10^6~.

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

6

Problem translated to English by Alex.