Problem
Max'in defterine "a" harflerinden oluşan, n uzunluğunda s ve m uzunluğunda t iki dizisi vardı; ve B" Latin alfabesi. Ayrıca Max, t dizisinin "abab..." şeklinde olduğunu, yani "a" harfinin dizinin tek sıralarında olduğunu ve &mdash harfinin "abab..." şeklinde olduğunu bilir. "b".
Aniden, sabah Max, birinin tellerini karıştırdığını keşfetti. Bazı s'ler "?" olarak değiştirildi.
i, i + 1, ..., i + m - 1 konumlarının sırasını, eğer 1 ≤&thinsp ise, t dizisinin s'deki oluşumu olarak adlandıralım ;i ≤ n - m + 1 ve t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
s dizisinin güzelliği, t dizisinin üst üste binmeyen maksimum oluşum sayısı olarak ölçülür. Max, "?" "a" üzerinde veya "b" (farklı konumlardaki karakterler farklı harflerle değiştirilebilir). Max, s dizisinin güzelliğinin olabildiğince büyük olması için ikameler yapmak istiyor. Tüm bu seçenekler arasından mümkün olduğunca az "?" karakterini değiştirmek istiyor. Kaç oyuncu değişikliği yapması gerektiğini öğrenin.
Giriş:
İlk satır tek bir tamsayı içerir n (1 ≤ n ≤ 10
5) — dizi uzunluğu s.
Girdinin ikinci satırı, yalnızca "a" harflerinden oluşan n uzunluğunda bir s dizisi içerir; ve B" Latin alfabesinin yanı sıra «?» sembolleri.
Üçüncü satır m tamsayısını içerir (1 ≤ m ≤ 10
5) — dizi uzunluğu t dizisinin kendisi "a" içerir; tek pozisyonlarda ve "b" çift sayılarda.
Çıktı:
Tek bir tamsayı yazdır — dizinin güzelliğini mümkün olan en yüksek düzeye çıkarmak için Vasya'nın yapması gereken minimum değişiklik sayısı.
Örnekler:
| Giriş |
Çıktı |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Açıklamalar:
İlk örnekte, t dizisi "a" biçimindedir. Tek ideal seçenek — tüm karakterleri değiştir "?" "a"ya.
İkinci örnekte, iki değiştirme kullanarak "aba?aba??" dizesini elde edebilirsiniz. İkiden fazla giriş alamazsınız.