题目描述

某座海岛上居住着一群原始部落居民，他们选择环形排列的 $m$ 个洞穴作为居所。这些洞穴顺时针编号为 $1,2,\dots ,m$。岛上有 $n$ 个部落成员，初始时分别住在洞穴 $C_1,C_2,\dots ,C_n$ 中。此后每年，第 $i$ 个成员会沿顺时针方向前进 $P_i$ 个洞穴并住下。

每个成员 $i$ 有一个寿命值 $L_i$，即他存活的年数。

经过长期观察发现，尽管岛上成员众多，但在任何人的有生之年中，从未有两名成员同时出现在同一个洞穴里，这使得小岛一直维持着和平。

科学家们想知道：维持这种和平局面，岛上至少需要多少个洞穴？

输入格式

第 $1$ 行为一个整数 $n(1\leq n\leq 15)$，即部落成员的数目。

第 $2$ 行到第 $n+1$ 行每行为三个整数 $C_i, P_i, L_i (1\leq C_i,P_i\leq 100, 0\leq L_i\leq 10^6 )$，表示每个成员的初始洞穴编号、每年走过的洞穴数及寿命值。

输出格式

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

样例

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\leq 10^6$