अधिकतम प्रश्न
Problem
मैक्स के पास उसकी नोटबुक में लंबाई n और t की लंबाई वाली दो स्ट्रिंग्स लिखी हुई थीं, जिसमें "a" अक्षर शामिल थे; और बी" लैटिन वर्णमाला। इसके अलावा, मैक्स जानता है कि स्ट्रिंग टी का रूप «abab...» है, अर्थात, अक्षर «a» स्ट्रिंग की विषम स्थिति पर है, और अक्षर — "बी"।
सुबह अचानक, मैक्स को पता चला कि किसी ने उसके तार को गड़बड़ कर दिया है। कुछ एस को "?" में बदल दिया गया है।
आइए स्थितियों के क्रम को कहते हैं i, i + 1, ..., i + m - 1 s में स्ट्रिंग t की घटना, अगर 1 ≤&thinsp ;i ≤ n - m + 1 और t1 = si, t2 &thinsp ;= si + 1, ..., tm = s i + m - 1.
स्ट्रिंग एस की सुंदरता को इसमें स्ट्रिंग टी की गैर-अतिव्यापी घटनाओं की अधिकतम संख्या के रूप में मापा जाता है। मैक्स कुछ "?" को बदल सकता है एक पर" या "बी" (विभिन्न पदों के वर्णों को विभिन्न अक्षरों से बदला जा सकता है)। मैक्स प्रतिस्थापन करना चाहता है ताकि स्ट्रिंग एस की सुंदरता जितनी बड़ी हो सके। इन सभी विकल्पों में से, वह यथासंभव कुछ "?" वर्णों को बदलना चाहती है। पता करें कि उसे कितने प्रतिस्थापन करने हैं।
इनपुट:
पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 105) — स्ट्रिंग की लंबाई एस।
इनपुट की दूसरी पंक्ति में लंबाई n की एक स्ट्रिंग होती है, जिसमें केवल "a" अक्षर होते हैं; और बी" लैटिन वर्णमाला, साथ ही प्रतीक «?».
तीसरी पंक्ति में पूर्णांक m (1 ≤ m ≤ 105) — स्ट्रिंग लंबाई टी. स्ट्रिंग टी में "ए" होता है; विषम स्थिति में, और "बी" सम संख्याओं पर।
आउटपुट:
एक पूर्णांक प्रिंट करें — स्ट्रिंग एस की सुंदरता को अधिकतम संभव बनाने के लिए वास्या द्वारा किए जाने वाले प्रतिस्थापनों की न्यूनतम संख्या।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
5
बीबी?ए?
1 |
2 |
9
अब ?? अब???
3
| 2 |
स्पष्टीकरण:
पहले उदाहरण में, स्ट्रिंग टी "ए" के रूप में है। एकमात्र इष्टतम विकल्प — सभी वर्ण बदलें "?" «a».
दूसरे उदाहरण में, दो प्रतिस्थापन का उपयोग करके, आप "अबा? अबा ??" स्ट्रिंग प्राप्त कर सकते हैं। आप दो से अधिक प्रविष्टियाँ प्राप्त नहीं कर सकते।