В 20 yy году Москва оказалась застроена до такой степени, что в черте города совсем не осталось территории, пригодной для постройки новых зданий. В поисках новых источников дохода правительство города приняло план, согласно которому все железнодорожные пути в черте города реконструируются и заменяются на подземные, а высвобожденная поверхность используется для коммерческой аренды.

Планирование будущей застройки было начато с участка Октябрьской железной дороги длиной в k метров. Так как строить здания поверх образованного туннеля — долгий и сложный процесс, было принято решение закрепить новый участок за наиболее популярными передвижными точками общепита, продающими мороженное, хот-доги, кофе и тому подобное.

Участок для строительства разделён на k сегментов одинаковой длины, последовательно пронумерованных целыми числами от 1 до k . Из n поступивших в правительство заявок на получение территории i -я претендует на сегменты с l _i по r _i , причём соответствующая точка общепита будет оказывать давление величиной p _i на соответствующий отрезок поверхности. Каждую заявку правительство либо отклонит, либо полностью удовлетворит, предоставив точке все запрошенные сегменты.

Правительство города заинтересовано в том, чтобы сдать каждый сегмент новообразованной территории в аренду хотя бы одной точке общепита. При этом, чтобы уменьшить риск обвала туннеля, было принято решение минимизировать максимальное из оказываемых давлений на каком-либо из сегментов. Обратите внимание, что не запрещается сдавать в аренду один сегмент сразу нескольким точкам общепита, но в таком случае давление, оказываемое ими на данный сегмент поверхности, суммируется.

Помогите правительству одобрить такой набор заявок, чтобы каждый сегмент был сдан в аренду хотя бы одной передвижной точке, но максимальное давление, оказываемое на туннель, было как можно меньше.