Монокарп играет в игру в жанре 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$$$ башен и остаться живыми. Монокарп хочет знать, какой суммарный запас здоровья будет у монстров после того, как они пройдут мимо всех башен.