Монокарп играет в игру в жанре tower defense. Уровень в этой игре может быть представлен как ось OX, на которой в каждой целочисленной точке от \(1\) до \(n\) стоит башня.
У башни в \(i\)-й точке вместимость маны равна \(c_i\), а скорость восстановления маны равна \(r_i\). В самом начале, до секунды \(0\), у каждой башни полная мана. Если в конце какой-то секунды у \(i\)-й башни \(x\) маны, то к началу следующей секунды становится \(\mathit{min}(x + r_i, c_i)\) маны.
На уровне появляются \(q\) монстров. \(j\)-й монстр появляется в точке \(1\) в начале \(t_j\)-й секунды и имеет \(h_j\) здоровья. Каждый монстр двигается со скоростью \(1\) точка в секунду в направлении увеличения координаты.
Когда монстр проходит мимо башни, башня наносит ему \(\mathit{min}(H, M)\) урона, где \(H\) — это текущий запас здоровья монстра, а \(M\) — текущий запас маны башни. Это количество вычитается из здоровья монстра и из маны башни.
К сожалению, некоторые монстры могут пройти мимо всех \(n\) башен и остаться живыми. Монокарп хочет знать, какой суммарный запас здоровья будет у монстров после того, как они пройдут мимо всех башен.
Выходные данные
Выведите одно целое число — суммарный запас здоровья у монстров, который будет после того, как они пройдут мимо всех башен.