Shenfe1 во время РО 2023 случайно попал на поляну ежей. Изначально на поляне нет ни одного ежа. Каждый из $$$n$$$ ($$$1 \leq n \leq 300$$$) ежей имеет три характеристики. $$$i$$$-й еж имеет три характеристики: $$$L_i$$$ ($$$1 \leq L_i \leq 10^8$$$), $$$C_i$$$ ($$$-10^8 \leq C_i \leq 10^8$$$) и скорость. Если $$$i \lt j$$$, то еж под номером $$$i$$$ быстрее ежа под номером $$$j$$$. Так же, гарантируется, что все $$$L_i$$$ уникальны.

В $$$L_i$$$-ю минуту еж $$$i$$$ приходит на поляну, и если он все еще на поляне, то через $$$T$$$ ($$$1 \leq T \leq 10^8$$$) минут он уйдет. Обратите внимание, все ежи находятся на поляне одинаковое количество времени, и что $$$i$$$-й еж еще будет находиться на поляне в момент времени $$$L_i + T$$$.

Shenfe1 может в любой момент времени, если на поляне есть хотя бы один еж, кинуть им еду. В таком случае, если на поляне $$$i$$$-й еж — самый быстрый еж, то он забирает еду и уходит, а к настроению Shenfe1 добавляется $$$C_i$$$ раздраженности. Временем броска еды, подбором еды и прихода/ухода ежа можно пренебречь.

Shenfe1 хочет знать, какую максимальную раздраженность в самом худшем случае он может получить, если изначально его раздраженность равна 0.