सेगमेंट को कवर करना
आपको
n सेगमेंट की एक सूची दी गई है, जिसमें हर सेगमेंट को के रूप में दर्शाया गया है और उसका लागत मान दिया गया है। साथ ही, आपके पास एक सेगमेंट [L, R] है, जिसे आपको पूर्ण रूप से कवर करना है।आपको
[L, R] को इस तरह कवर करना चाहिए कि चयनित सेगमेंट्स का संयुक्त हिस्सा [L, R] को समाहित कर ले। ध्यान दें कि अगर आप i-वाँ सेगमेंट चुनते हैं, तो उसकी लागत को वहन करना होगा।आपका कार्य इस बात का पता लगाना है कि
[L, R] सेगमेंट को कवर करने के लिए आपको न्यूनतम कुल लागत कितनी चुकानी होगी।इनपुट
इनपुट की पहली पंक्ति में तीन पूर्णांक
n, L और R होते हैं (1 ≤ n ≤ 100 000, 1 ≤ L ≤ R ≤ ), जहाँ n सेगमेंट्स की संख्या दर्शाता है और [L, R] वह क्वेरी सेगमेंट है जिसे कवर किया जाना है।इसके बाद की
n पंक्तियों में तीन मान , और दिए होते हैं (1 ≤ l_i ≤ r_i ≤ 10^9, 1 ≤ w_i ≤ 10^9), जो एक सेगमेंट और उसकी लागत का विवरण देते हैं।आउटपुट
कार्यक्रम को एक एकल पूर्णांक प्रिंट करना चाहिए, जो
[L, R] सेगमेंट को कवर करने की न्यूनतम लागत हो। यदि [L, R] को कवर करना संभव न हो, तो -1 प्रिंट करें।उदाहरण
इनपुट | आउटपुट |
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