Հատվածի ծածկում
Ձեզ տրված է
n հատվածներից բաղկացած ցուցակ, որոնցից յուրաքանչյուրն ունի տեսք և իր արժեքը ։ Բացի այդ, գոյություն ունի նաև հատված, որը անհրաժեշտ է ամբողջությամբ փակել (ծածկել):Հարկավոր է ընտրել ցուցակում առկա հատվածներից այնպիսի բազմություն, որ այդ հատվածների միավորումը ընդգրկի հատվածը։ Սակայն նկատի ունեցեք, որ
i-րդ հատվածը ընտրելու դեպքում առաջանում է ծախս։Գտեք, թե որ նվազագույն գումարով կարելի է ծածկել հատվածը։
Մուտք
Մուտքի առաջին տողում տրված են
n, L և R ամբողջ թվերը (1 ≤ n ≤ 100000, 1 ≤ L ≤ R ≤ 10^9), որոնք նշում են segment-ների քանակը և ծածկման համար անհրաժեշտ [L, R] հատվածը։Հաջորդ
n տողերից յուրաքանչյուրում տրված են l_i, r_i և w_i (1 ≤ li ≤ ri ≤ 10^9, 1 ≤ w_i ≤ 10^9), որոնք بیانում են տվյալ հատվածի սկզբնային և վերջնական սահմանները, ինչպես նաև դրա արժեքը։Ելք
Ծրագիրը պետք է տպի
[L, R] հատվածը ծածկելու համար պահանջվող նվազագույն գումարը։ Եթե [L, R] հատվածը ծածկելը հնարավոր չէ, հարկավոր է տպել -1։Օրինակներ
Ելք | Output |
5 3 10
1 3 2
1 5 5
3 7 4
6 10 3
5 10 5 | 9 |
3 1 5
1 2 4
1 3 7
2 4 3 | -1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB