4.荒岛野人

题目描述

有排列成环行的 $M$ 个山洞。这些山洞顺时针编号为 $1$ , $2$ , $\ldots$ , $M$ 。

岛上有 $N$ 个野人，一开始依次住在山洞 $C_{1}$ , $C_{2}$ , $\cdots$ , $C_{N}$ 中，以后每年，第 $i$ 个野人会沿顺时针向前走 $P_{i}$ 个洞住下来。每个野人 $i$ 有一个寿命值 $L_{i}$ ，即生存的年数。

下面四幅图描述了一个有 $6$ 个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 $1$ , $2$ , $3$ ；每年要走过的洞穴数依次为 $3$ , $7$ , $2$ ；寿命值依次为 $4$ , $3$ , $1$ 。

请问，至少有多少个山洞，才能使没有任何两个野人在有生之年处在同一个山洞中？

第一行为一个整数 $N$ ，即野人的数目；

第二行到第 $N+1$ 行每行为三个整数 $C_{i}$ , $P_{i}$ , $L_{i}$ ，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

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

对于 $100\%$ 的数据， $1 \leq N \leq 15$ ， $1 \leq C_{i},P_{i} \leq 100$ ， $0 \leq L_{i} \leq 10^{6}$ 。