Yol#5279
Nastya yeməkxanadan tədris binasına doğru gedir və yolda uzaq şəhərlərdəki dostlarına SMS göndərir. Cavablar tez-tez gəldiyi üçün Nastya hər -cı addımda bir SMS göndərməlidir. Yolun üzərində Nastyanın temperaturunu bəzi dərəcə artıran günəşli sahələr və onun temperaturunu azaldan suvarma qurğuları var.
Hava çox isti olduğundan, Nastya yolun sonunda mümkün olan ən aşağı temperaturda olmaq istəyir. Nastya mümkün qədər tez çatmaq istəyir, buna görə də yalnız binaya doğru gedir.
Birinci sətrdə üç tam ədəd (1 \leq n \leq 1000), (1 \leq k \leq x) və (0 \leq x \leq 1000) — obyektlərin (günəşli sahələr və suvarma qurğuları), dayanacaqlar arasındakı maksimum addım sayı və Nastyanın yolunun uzunluğu (addımlarla) verilir. Sonra gələn sətrin hər birində üç tam ədəd: l_i, r_i (1 \leq l_i, r_i \leq x) və d_i (-10000 \leq d_i \leq 10000) — müvafiq obyektə uyğun yol seqmentinin koordinatları və bu seqmentdə dayanarkən Nastyanın temperaturunda baş verən dəyişiklik. Heç bir iki seqment üst-üstə düşmür.
Yeganə tam ədəd çıxarın — Nastyanın yolun sonunda əldə edə biləcəyi minimal mümkün temperatur dəyişikliyi.
Nümunə 1
Nümunə 2
Nümunə 3