PEG Judge - NOI '02 - Island of Cavemen

National Olympiad in Informatics, China, 2002

Day 2, Problem 1 - Island of Cavemen

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, …, M in clockwise order. There are N cavemen living on the island, initially located in caves C₁, C₂, …, 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 Format

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

Output Format

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⁶.