Module: लालची एल्गोरिदम

Problem

रिसोट्टो नीरो को मैग्नेटिक कंस्ट्रक्टर से घर इकट्ठा करना पसंद है।
इसके n भाग हैं, i-वें का आकार s_i है। 
एक घर बनाने के लिए, आपको कुछ समान आकार के ठीक a भागों की आवश्यकता होती है और ठीक b अन्य समान आकार के भागों की, जो k गुना बड़ा होता है।

निर्धारित करें कि रिसोट्टो नीरो अधिकतम कितने घर बना सकता है।

इनपुट:
पहली पंक्ति में पूर्णांक n, a, b और k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000) हैं।
दूसरी पंक्ति में भाग आकार का क्रम होता है — पूर्णांक s₁, s₂, …, s_n (1 ≤ s_i ≤ 10 < sup>6).

आउटपुट:
एक पूर्णांक प्रिंट करें — n दिए गए हिस्सों से बनाए जा सकने वाले घरों की अधिकतम संख्या।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6 3 14 1 1 3
3 3 1 1 9 9 2 3 6 6 3 18 3 18 6 1 2 3 10
1000000 0
व्याख्या:
पहले उदाहरण में, सबसे अच्छा विकल्प [1, 2, 2] आयामों वाले हिस्सों से दो घर बनाना और [3, 6, 6] आयामों वाले हिस्सों से एक घर बनाना है।