Module: पुनरावर्ती गणना

Problem

हैंडसम जैक अपना इरीडियम प्रोसेसिंग प्लांट लगाना चाहता है।
जैक के नियंत्रण में n कारखाने हैं, उनमें से प्रत्येक को 1 से n तक क्रमांकित किया गया है। प्रत्येक संयंत्र एरिडियम जमा पर स्थित है, जहां इसे संयोजन में भी खनन किया जाता है। और फ़ैक्टरी संख्या जितनी अधिक होगी, वह उतनी ही नई होगी।

प्रत्येक संयंत्र का अपना दक्षता सूचकांक a_i होता है। यह धनात्मक, ऋणात्मक या शून्य हो सकता है।

प्रत्येक संयंत्र को एरीडियम अयस्क को संसाधित करना चाहिए। आप पाइपलाइन के माध्यम से अपने स्वयं के जमा का उपयोग कर सकते हैं या किसी अन्य संयंत्र द्वारा पूर्व में संसाधित अयस्क ले सकते हैं। हालाँकि, यह प्रक्रिया कुछ सीमित है। सबसे पहले, पाइपलाइन प्रणाली को अधिभारित नहीं करने के लिए, प्रत्येक संयंत्र एक दूसरे से सख्ती से आगे की प्रक्रिया के लिए अयस्क को स्वीकार कर सकता है (या स्वीकार नहीं करता है और अपनी जमा राशि का उपयोग करता है)। दूसरे, पुराने संयंत्र नए संयंत्र के बाद अयस्क के पुनर्संसाधन के लिए तकनीकी रूप से सक्षम नहीं होते हैं।

पूरे सिस्टम के अंतिम प्रदर्शन की गणना निम्नानुसार की जाती है: प्रत्येक संयंत्र के लिए, इसकी दक्षता a_i ली जाती है और प्रसंस्करण चरण से गुणा की जाती है, जिसकी गणना आने वाले अयस्क को संसाधित करने के समय की संख्या के रूप में की जाती है। (अधिक विवरण के लिए, उदाहरणों के लिए स्पष्टीकरण देखें), फिर सभी प्राप्त मूल्यों को सभी पौधों के लिए संक्षेप में प्रस्तुत किया जाता है।

हैंडसम जैक को सिस्टम को व्यवस्थित करने में मदद करें ताकि पूरे सिस्टम का समग्र प्रदर्शन जितना संभव हो उतना उच्च हो।

इनपुट:
पहली पंक्ति में एक प्राकृतिक संख्या होती है n (1 <= n <= 7) - कारखानों की संख्या।
दूसरी पंक्ति में n स्थान-पृथक पूर्णांक होते हैं, जहाँ i-th संख्या a_i (-1000 <= a_i <= 1000) - आधार दक्षता है i.
के तहत पौधे का
आउटपुट:
एक नंबर प्रिंट करें - पूरे सिस्टम का अधिकतम संभव कुल प्रदर्शन।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 3
1 5 3 20 3
1 5 -3 8
स्पष्टीकरण:
पहले उदाहरण में, पहले संयंत्र के लिए अपने स्वयं के अयस्क का खनन करना सबसे अधिक लाभदायक है, दूसरा संयंत्र पहले से अयस्क प्राप्त करता है, और तीसरा संयंत्र दूसरे से प्राप्त करता है। इस मामले में, पहला संयंत्र प्राथमिक प्रसंस्करण करता है और इसकी उत्पादकता 1 * 1 = 1 है। दूसरा संयंत्र माध्यमिक प्रसंस्करण करता है, इसकी उत्पादकता 5 * 2 = 10 है। और तीसरा संयंत्र तीसरी बार प्राप्त अयस्क को संसाधित करता है, इसलिए इसकी उत्पादकता 3 * 3 = 9 है। कुल प्रदर्शन 1 + 10 + 9 = 20 है।
कृपया ध्यान दें कि इस उदाहरण में, दूसरे और तीसरे पौधों की अदला-बदली नहीं की जा सकती, क्योंकि दूसरा संयंत्र तकनीकी कारणों से तीसरे के बाद अयस्क का प्रसंस्करण नहीं कर पाएगा, क्योंकि यह तीसरे से पुराना है।

दूसरे उदाहरण में, पहला और तीसरा कारखाना अपनी जमा राशि का उपयोग करेगा, और दूसरा कारखाना पहले से अयस्क प्राप्त करेगा।