题目描述

岛上有 m 个洞穴，顺时针编号为 1∼m。岛上有 n（1≤n≤15）个野人分别住在 $c_1,c_2,…,c_n （1≤c_i≤100）$ 中。以后每年，第 i 个野人会沿顺时针向前走 $p_i （1≤p_i≤100）$ 个洞住下来，其中第 i 个野人可以生存 $l_i$ 年。没有 2 个野人能在有生之年生存在同一个洞穴中，求洞穴个数 m（m≤106）的最小值。

输入格式

第1行为一个整数 N（1<=N<=15），即野人的数目。 第2行到第 N+1 每行为三个整数 Ci,Pi,Li 表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。 （1<=Ci，Pi<=100，0<=Li<=10^6）。

输出格式

仅包含一个数 M，即最少可能的山洞数。输入数据保证有解，且M不大于 $10^6$。

3
1     3      4
2     7      3
3     2      1

6
//该样例对应于题目描述中的例子。

提示

没有写明提示。

题目来源

鸣谢刘汝佳先生授权使用。