पानी की बाल्टियाँ

दो बाल्टियों (pails) के आकार x और y दिए गए हैं। आपका लक्ष्य है कि इन दोनों बाल्टियों में पानी की कुल मात्रा लक्षित मान s के यथासंभव निकट हो।

आपको अधिकतम k बार निम्नलिखित क्रियाएं करने की अनुमति है:

• किसी एक बाल्टी को पूरा भर दें।

• किसी एक बाल्टी को पूरी तरह खाली कर दें।

• एक बाल्टी से दूसरी बाल्टी में पानी डालें, जब तक कि दूसरी बाल्टी भर न जाए या पहली बाल्टी खाली न हो जाए (जो पहले हो जाए)।

शुरुआत में, दोनों बाल्टियाँ खाली होती हैं।

संभव है कि आप दोनों बाल्टियों में ठीक s मात्रा न प्राप्त कर पाएं, इसलिए आपको |s - s'| का सबसे छोटा मान खोजने के लिए कहा गया है, जहाँ s' दोनों बाल्टियों में मौजूद कुल पानी की मात्रा है।

इनपुट

इनपुट की एकमात्र पंक्ति में 4 पूर्णांक x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100), और s (1 ≤ s ≤ 200) शामिल होंगे।

आउटपुट

कार्यक्रम को वह न्यूनतम संभव अंतर प्रिंट करना चाहिए, जिसे अधिकतम k क्रियाएं करके हासिल किया जा सकता है।

उदाहरण

व्याख्या

हमें केवल 2 क्रियाएं करने की अनुमति है। इसलिए, 2 क्रियाओं के बाद संभावित परिणाम इस प्रकार हैं:

1. (0, 0) → 0 units

2. (14, 0) → 14 units

3. (0, 50) → 50 units

4. (0, 14) → 14 units

5. (14, 36) → 50 units

6. (14, 50) → 64 units

इसमें 32 के सबसे निकट 14 है, जिसके कारण अंतर 18 रहता है।

ध्यान दें कि (14, 36) की स्थिति से पहली बाल्टी को खाली कर 36 प्राप्त करना संभव था, लेकिन इसके लिए 3 क्रियाएं आवश्यक पड़तीं; जबकि अधिकतम 2 क्रियाएं ही अनुमत हैं।