\(N\) людей розташовані в колі з \(M\) стільців. Кожна людина має свій початковий стілець (стільці пронумеровані від 1 до M).
Кожну секунду, всі люди переміщаються на певну кількість стільців за годинниковою стрілкою (в кожної людини це число може бути різне).
Для кожної людини відомо скільки секунд вона грає в цю гру (після цього вона виходить з кола).
Визначіть найменше можливе \(M\) при якому під час гри жодні дві людини не опиняться одночасно на одному стільці.
Гарантується, що відповідь завжди є і вона не перевищує \(10^6\)

Формат вхідних даних

В першому рядку число \(N\) - кількість людей (\(1 \le N \le 15\))
В кожному з наступних \(N\) рядків по три цілих числа \(Ai,Bi,Ci\), \(Ai\) - початковий стілець людини, \(Bi\) - на скільки стільців вона зміщується щосекунди, \(Ci\) - скільки секунд вона в грі.
(\(1 \le Ai,Bi \le 100\), \(0 \le Ci \le 10^6\))

Формат вихідних даних

Виведіть мінімальне можливе \(M\) - кількість стільців в колі при якому під час гри жодні двоє людей не опиняться одночасно на одному стільці.

Приклад вхідних даних

3
1 3 4
2 7 3
3 2 1

Приклад вихідних даних

6