题目描述

克里特岛上有 $m$ 个环形排列的山洞（编号 $1$ 到 $m$），住着 $n$ 个野人。
第 $i$ 个野人初始在山洞 $C_i$，每年沿顺时针走 $P_i$ 个洞住下，寿命为 $L_i$ 年。
要求没有任何两个野人在有生之年住在同一个山洞，求满足条件的最少山洞数 $M$。

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

输入格式

第一行一个整数 $n$，表示野人数。
接下来 $n$ 行，每行三个整数 $C_i, P_i, L_i$。

输出格式

一行一个整数 $M$，表示最少山洞数。

3
1 3 4
2 7 3
3 2 1

6

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n \leq 15$
• $1 \leq C_i, P_i \leq 100$
• $0 \leq L_i \leq 10^6$
• 答案 $M$ 不超过 $10^6$，且输入数据保证有解。

本题改编自 NOI 2002