C. Перун, ультуй!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Многие студенты с пользой проводят новогодние каникулы. Влад особенно преуспевает в этом! Третьи сутки напролет, держась на салатах и мандаринах, оставшихся с новогоднего стола, он калибрует ранг в своей любимой MOBA-игре, играя за героя по имени Перун.

Абсолютная способность Перуна — «Гнев грома» — при применении мгновенно отнимает у каждого из n врагов на карте по очков здоровья в качестве единовременного эффекта. У нее есть ограничение — она может быть активирована только в момент времени, являющийся целым числом. Награда за убийство врага изначально равна и увеличивается каждую секунду на . Формально, если после применения «Гнева грома» в секунду t здоровье врага i станет меньшим или равным нулю, то Влад получит золота за его убийство.

Каждый враг может получать урон, а может восполнять здоровье — и все это множеством различных способов. Влада, впрочем, не интересуют детали; для каждого из n героев он лишь знает:

  •  — максимальное количество очков здоровья героя i;
  •  — количество очков здоровья героя в секунду 0;
  •  — количество очков здоровья, которое герой i восстанавливает за одну секунду (очки добавляются сразу же по наступлении следующей секунды).

Еще Влад знает о m изменениях здоровья в ходе игры:

  •  — секунда, в которую изменяется здоровье врага;
  •  — враг, у которого изменяется здоровье;
  •  — новое количество очков здоровья врага enemyj.

Естественно, из игры Влад хочет вынести максимум пользы и, если потребуется, он, забыв об учебе, будет выжидать годы и годы в ожидании подходящего момента для активации суперспособности. Помогите ему найти секунду от 0 включительно до  + ∞ включительно (напомним, что номер секунды должен быть целым числом), чтобы активация «Гнева грома» помогла ему получить максимальное количество золота, и выведите это количество.

Входные данные

В первой строке заданы два целых числа, разделенных пробелами — n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105).

Во второй строке заданы три целых числа, разделенных пробелами — , , (, ).

В последующих n строках заданы три целых числа, разделенных пробелами — , , (, ).

В последующих m строках заданы три целых числа, разделенных пробелами — , , (, , ). Гарантируется, что в одну секунду для одного врага известно не более одного изменения здоровья: формально для любых a, b таких, что 1 ≤ a, b ≤ m, a ≠ b верно, что если , то .

Выходные данные

Выведите в одной строке единственное число — максимальное количество золота, которое Влад может получить в результате единовременного применения способности «Гнев грома», или -1, если количество золота, которое он может получить, может быть бесконечно большим.

Примеры
Входные данные
3 2
1000 10 50
70 5 5
90 70 1
110 20 2
20 2 10
30 3 10
Выходные данные
3000
Входные данные
1 1
500 50 1000
750 750 20
10 1 300
Выходные данные
-1
Примечание

На графиках ниже изображены очки здоровья каждого из врагов в зависимости от времени в примерах.

Желтым цветом обозначено время, в течение которого Влад может убить одного врага.

Фиолетовым цветом обозначено время, в течение которого Влад может убить двух врагов.

В первом примере можно применить «Гнев грома» в 50-ю секунду: погибнут враги 2 и 3, так как у них будет 40 и 50 очков здоровья соответственно, и Влад получит награду в 2·(1000 + 50·10) = 3000 золота.

Во втором примере максимальное здоровье врага 1 меньше урона, наносимого способностью, поэтому его можно будет убить в любой момент времени, а поскольку награда увеличивается каждую секунду на 50 золота, то максимально возможная награда будет увеличиваться до бесконечности.