Module: गतिशील प्रोग्रामिंग में पैटर्न

Problem

आपको n पूर्णांकों की एक सरणी दी गई है। आपको इसे k गैर-खाली उपखंडों (लगातार तत्वों का एक क्रम) में विभाजित करने की आवश्यकता है ताकि:
1) सरणी के प्रत्येक तत्व को ठीक एक उपखंड में शामिल किया गया था।
2) यदि प्रत्येक उपखंड के लिए हम इसमें न्यूनतम संख्या चुनते हैं, तो सभी निम्नतम का योग अधिकतम संभव होना चाहिए।

इस विभाजन के उपखंडों में मानों के न्यूनतम योग की रिपोर्ट करें।

इनपुट:
पहली पंक्ति में दो प्राकृतिक संख्याएँ हैं - n (1 <= n <= 500) और k (1 <= k <= n)।
दूसरी पंक्ति में n पूर्णांक हैं - सरणी a_i के तत्व (1 <= a_i <= 10⁵).< बीआर />
आउटपुट:
एक नंबर प्रिंट करें - समस्या का जवाब।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 5 3
4 2 5 1 3 8
व्याख्या:
उपयुक्त विभाजनों में से एक: [4, 2], [5], [1, 3]। प्रत्येक उप-खंड में न्यूनतम का योग 2 + 5 + 1 = 8 है।