Masala #2KV3SK0MEA

Shaxboz va uning \(n-1\) ta do'sti 8-mart “Xalqaro xotin-qizlar kuni” munosabati bilan, kursdosh qizlariga sovg'a olish uchun do'konga kelishdi. Ular do'kondan jami \(p\) ta sovg'a olishdi. Do'konda \(1\) dan \(k\) gacha raqamlangan \(k\) ta kassa bor. Har bir i-kassa sotuvchisi bitta sovg'ani hisoblash uchun \(x_i\) vaqt sarflaydi, i-kassa sotuvchisi barcha xaridlar uchun \(y_i\) vaqt ichida xaridordan to'lovni qabul qilib bo'ladi, ayni paytda Shaxboz yoki uning do'stlariga i-kassadagi navbat kelishi uchun \(t_i\) vaqt ketadi.

Shaxboz va uning do'stlari kassalarga shunday navbatda turishlari va sovg'alarni shunday bo'lib olishlari kerakki, ular do'kondan to'liq chiqib ketishlari uchun eng minimal vaqt sarflashlari kerak. (Sovg'asiz turgan xaridor kassa oldidan vaqt sarflamasdan o'tib ketishi mumkin.) 
Sizning vazifangiz ularning barchasi do'kondan chiqib ketishlari mumkin bo'lgan eng minimal vaqtni hisoblashdan iborat.

Birinchi satrda \(k\) butun soni do'kondagi kassalar soni kiritiladi.

Keyingi \(k\) ta satrda 3 tadan butun sonlar \(x_i\) - \(i\)-kassa sotuvchisi har bir sovg'ani ro'yxatdan o'tkazishi uchun ketadigan vaqt, \(y_i\) - i-kassa sotuvchisi hozirgi xaridordan xaridlar uchun to'lovni qabul qilishi uchun ketadigan vaqt, \(t_i\) - i-kassadagi navbat tugashi uchun ketadigan vaqt.

Keyingi qatorda Shaxboz va do'stlarining umumiy soni \(n\) va ular olgan sovg'alar soni \(p\) kiritiladi.

\(1\leq n , k \leq 10^{5}\)

\(1 \leq x_i , y_i , t_i \leq 10^{5}\)

\(1 \leq p \leq 10^{6}\)

Shaxboz va do'stlari do'konni tark etishlari uchun kerak bo'ladigan minimal vaqt miqdorini chop eting.