बांस के पेड़ बेचना
आपके पास एक बांस का पेड़ है। यह अलग-अलग दिनों में अलग-अलग गति से बढ़ता है। आप इसे काटकर और बेचकर कुछ पैसा कमाना चाहते हैं (पेड़ काटने के बाद भी बढ़ना जारी रखता है)।
बांस की लंबाई दिन 1 पर 0 होती है और यह
n दिनों तक बढ़ता है। आपको पता है कि प्रत्येक दिन बांस के प्रति मीटर की कीमत कितनी है और बेचने से एक रात पहले यह कितने मीटर बढ़ेगा।
हर दिन आप या तो पूरे पेड़ को काटकर बेच सकते हैं (काटने के बाद भी यह बढ़ता रहेगा), या इसे आगे बढ़ने के लिए छोड़ सकते हैं। आपके लिए अधिकतम कमाई कितनी हो सकती है?
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ ) होता है, जो दिनों की संख्या दर्शाता है।अगली
n पंक्तियों में दो स्पेस से अलग किए गए पूर्णांक (, ) दिए होते हैं (1 ≤ , ≤ )। इनमें उस मीटर की संख्या बताता है, जितना पेड़ बेचने से एक रात पहले बढ़ेगा, और दिन i पर बांस के प्रति मीटर की कीमत दर्शाता है।आउटपुट
प्रोग्राम को अधिकतम वह राशि प्रदर्शित करनी चाहिए जो बांस को उगाने और बेचने से प्राप्त हो सकती है। यह गारंटी दी जाती है कि उत्तर से अधिक नहीं होगा।
उदाहरण
Input | Output |
8
7 2
1 4
3 3
5 5
4 2
2 5
7 4
1 1 | 139 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB