Магазин целых чисел продаёт \(n\) отрезков, \(i\)-й из которых состоит из чисел от \(l_i\) до \(r_i\) и стоит \(c_i\) монет.
Завтра Вася отравится в этот магазин и купит несколько отрезков. Он получит все числа, лежащие хотя бы в одном из выбранных отрезков. Количество монет, которое он потратит на покупку равно сумме стоимостей отрезков, которые он купит.
В качестве подарка за покупку, Вася дополнительно получит ещё несколько целых чисел. Число \(x\), не купленное Васей ранее, он получит тогда и только тогда, когда для \(x\) выполняются два следующих условия:
- Найдётся купленное Васей число \(l\), меньшее \(x\).
- Найдётся купленное Васей число \(r\), большее \(x\).
Число \(x\) Вася может получить в подарок не более одного раза, таким образом все числа, которые получит Вася будут различными.
Например, если Вася купит отрезок \([2, 4]\) за \(20\) монет и отрезок \([7, 8]\) за \(22\) монеты, он потратит \(42\) монеты и получит числа \(2, 3, 4, 7, 8\) как содержимое отрезков. В качестве подарка он получит числа \(5\) и \(6\).
По техническим причинам, завтра в магазине будут доступны к покупке только \(s\) первых отрезков (то есть отрезки \([l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]\)). Вася не сможет купить отрезки, не доступные к покупке.
Вася хочет получить (купить или получить в подарок) как можно больше целых чисел. Если это можно сделать разными способами, то он выберет самый дешёвый из них.
Для всех значений \(s\) от \(1\) до \(n\) определите, сколько монет потратит Вася, если к покупке будут доступны только \(s\) первых отрезков.
Примечание
В первом наборе входных данных при \(s = 1\) Вася может купить только один отрезок \([2, 4]\) за \(20\) монет и получить \(3\) числа.
Способ получить \(7\) чисел за \(42\) монеты при \(s = 2\) описан в условии.
Во втором наборе входных данных обратите внимание на то, что в магазине могут быть одинаковые отрезки.