Многие студенты с пользой проводят новогодние каникулы. Влад особенно преуспевает в этом! Третьи сутки напролет, держась на салатах и мандаринах, оставшихся с новогоднего стола, он калибрует ранг в своей любимой MOBA-игре, играя за героя по имени Перун.
Абсолютная способность Перуна — «Гнев грома» — при применении мгновенно отнимает у каждого из n врагов на карте по 
очков здоровья в качестве единовременного эффекта. У нее есть ограничение — она может быть активирована только в момент времени, являющийся целым числом. Награда за убийство врага изначально равна 
и увеличивается каждую секунду на 
. Формально, если после применения «Гнева грома» в секунду t здоровье врага i станет меньшим или равным нулю, то Влад получит 
золота за его убийство.
Каждый враг может получать урон, а может восполнять здоровье — и все это множеством различных способов. Влада, впрочем, не интересуют детали; для каждого из n героев он лишь знает:
-
— максимальное количество очков здоровья героя i; -
— количество очков здоровья героя в секунду 0; -
— количество очков здоровья, которое герой i восстанавливает за одну секунду (очки добавляются сразу же по наступлении следующей секунды).
Еще Влад знает о m изменениях здоровья в ходе игры:
-
— секунда, в которую изменяется здоровье врага; -
— враг, у которого изменяется здоровье; -
— новое количество очков здоровья врага enemyj.
Естественно, из игры Влад хочет вынести максимум пользы и, если потребуется, он, забыв об учебе, будет выжидать годы и годы в ожидании подходящего момента для активации суперспособности. Помогите ему найти секунду от 0 включительно до + ∞ включительно (напомним, что номер секунды должен быть целым числом), чтобы активация «Гнева грома» помогла ему получить максимальное количество золота, и выведите это количество.
Выходные данные
Выведите в одной строке единственное число — максимальное количество золота, которое Влад может получить в результате единовременного применения способности «Гнев грома», или -1, если количество золота, которое он может получить, может быть бесконечно большим.
Примечание
На графиках ниже изображены очки здоровья каждого из врагов в зависимости от времени в примерах.
Желтым цветом обозначено время, в течение которого Влад может убить одного врага.
Фиолетовым цветом обозначено время, в течение которого Влад может убить двух врагов.
В первом примере можно применить «Гнев грома» в 50-ю секунду: погибнут враги 2 и 3, так как у них будет 40 и 50 очков здоровья соответственно, и Влад получит награду в 2·(1000 + 50·10) = 3000 золота.
Во втором примере максимальное здоровье врага 1 меньше урона, наносимого способностью, поэтому его можно будет убить в любой момент времени, а поскольку награда увеличивается каждую секунду на 50 золота, то максимально возможная награда будет увеличиваться до бесконечности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1000 10 50
70 5 5
90 70 1
110 20 2
20 2 10
30 3 10
|
3000
|
|
2
|
1 1
500 50 1000
750 750 20
10 1 300
|
-1
|