Հատվածի ծածկում

Ձեզ տրված է 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։

Օրինակներ