Radio Towers
Балканска Олимпиада по Информатика 2015
Time Limit: 0.5s, Memory Limit: 64MiB
Границата между България и Румъния е река Дунав. Тъй като е възможно тя да бъде премината с лодка и от време на време хора преминават нелегално от едната държава в другата, по брега на реката са разположени N охранителни кули. Техните позиции са на разстояние X1, X2, …, XN метра по течението на реката, считано от мястото, където тя навлиза в България. За простота ще си представим Дунав като отсечка, а кулите – като точки с целочислени координати по нея.

Във всяка кула i има радио-предавател със сила Pi, чрез който може да се комуникира с някои (потенциално всички или никоя) от останалите. Две кули i и j могат да комуникират помежду си ако сумарната сила на предавателите им е по-голяма или равна на разстоянието между тях, тоест: |XiXj| ≤ Pi + Pj.

Поради факта, че и двете държави са в Европейския съюз, бе взето решение някои от кулите да бъдат изведени от експлоатация. Планът е да бъдат оставени само K на брой от тези кули, а другите да бъдат продадени. Продаването на кула i носи на държавата Si лева, но кулата вече не може да бъде използвана.

Освен това, за по-добро охраняване на границата е въведено ново изискване всеки две от оставените K кули да могат да комуникират директно помежду си. Тъй като това потенциално не е възможно със сегашните им предаватели, те могат да бъдат модернизирани, като така се подобрява тяхната сила. За увеличаването на силата на произволна кула с единица е нужен един лев. Ели наскоро започна стаж в министерството на финансите. Сега тя иска да блесне там, като предложи най-изгоден план за продажбата на N-K кули и подновяване на останалите, така че всеки две от тях да могат да комуникират директно помежду си. Вие решавате да й помогнете, като напишете програма, която намира минималната цена (или максимална печалба, ако в резултат на продажбите бъдат спечелени повече пари, отколкото са изхарчени за обновяването) за извършване на задачата.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и K – съответно броят кули преди и след приватизацията. Всеки от следващите N реда ще съдържа по три цели числа – Xi Pi Si – съответно позицията на кулата, сила на нейния предавател в началото и цената, за която може да бъде продадена. Кулите са дадени в нарастващ ред на позицията им Xi. Никои две кули не се намират на една и съща позиция.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималната цена (или максималната печалба) за извършване на задачата. В случай на печалба, изведеното от Вас число трябва да е отрицателно.
Ограничения
  • 1 ≤ KN ≤ 100,000
  • 1 ≤ Xi, Pi, Si ≤ 1,000,000,000
Примерен Вход Примерен Изход
5 3 4 63 3 13 2 4 87 3 9 121 6 15 159 5 2 42
9 5 5 8 4 10 10 7 11 9 7 13 6 6 19 20 9 20 2 1 23 1 3 26 13 11 28 4 2-24
В първия пример един оптимален вариант е да оставим кулите {1, 3, 4}. За целта трябва да увеличим силата на кула 1 със 17, и на кула 4 с 31, заплащайки 17 + 31 = 48 лева. От продажбата на кулите 2 и 5 печелим 4 + 2 = 6 лева. Така общо заплащаме 48 – 6 = 42 лева.
Във втория пример избирайки, например, кулите с индекси {2, 3, 6, 7, 9}, може да бъде постигната печалба в размер на 24 лева. За да могат те да комуникират една с друга увеличаваме силата на 7 с 2, а тази на 9 с 4, за цена 2 + 4 = 6. При този избор на кули можем да продадем {1, 4, 5, 8} за 4 + 6 + 9 + 11 = 30 лева, като сумарната "цена" е 6 – 30 = -24 лева.
Мрън!