Archiwum zadań programistycznych WWSI

Jak powszechnie wiadomo, każdy ma swoją taktykę, z której korzysta podczas gry w kamień, papier i nożyce. Staś na przykład zawsze używa tej samej kolejności znaków, Grześ natomiast w każdej rozgrywce wykorzystuje maksymalnie k razy kamień, p razy papier oraz n razy nożyce. Staś z Grzesiem właśnie założyli się o to czyja metoda jest lepsza. Ponieważ jesteś kolegą zarówno Grzesia jak i Stasia postanowiłeś pomóc im w rozwiązaniu sporu i napisać program który obliczy maksymalną liczbę kolejnych remisów jaka może paść w trakcie rozgrywki - taka wiedza zdecydowanie ułatwi im dalsze rozważania.

Napisz program, który na podstawie kolejności znaków używanych przez Stasia oraz wartości zmiennych k, p i n obliczy maksymalną liczbę kolejnych remisów jakie paść mogą w trakcie rozgrywki.

Wejście

W pierwszej linii wejścia znajdują się cztery liczby: k, p, n oraz r (0 ≤ k, p, n ≤ 10⁶, k + p + n = r). Pierwsze trzy oznaczają odpowiednio ile razy Grześ może użyć znaków: kamienia, papieru oraz nożyc. Liczba r opisuje długość sekwencji znaków używanych przez Stasia w każdej rozgrywce. W kolejnej linii znajduje się wyraz o długości r składający się z liter k, p oraz n.

Wyjście

Na wyjściu należy wypisać maksymalną liczbę kolejnych remisów jakie mogą paść.

Przykład

Wejście

1 1 4 6
kkppnn

Wyjście

3