После долгой вечеринки Петя захотел поехать домой, но обнаружил себя в другом конце города. В городе есть \(n\) перекрестков, расположенных в ряд, и на каждом перекрестке есть остановка, на которой можно сесть либо на автобус, либо на троллейбус.
Перекрестки можно задать как строку \(s\) длины \(n\), где \(s_i = \texttt{A}\), если на \(i\)-м перекрестке есть автобусная станция, и \(s_i = \texttt{B}\), если на \(i\)-м перекрестке есть троллейбусная станция. Сейчас Петя находится на первом перекрестке (которому соответствует \(s_1\)), и ему нужно попасть на последний перекресток (которому соответствует \(s_n\)).
Если для двух перекрестков \(i\) и \(j\) на всех перекрестках \(i, i+1, \ldots, j-1\) есть автобусная остановка, то можно заплатить \(a\) рублей за билет на автобус, и доехать с \(i\)-й остановки до \(j\)-й (на \(j\)-й остановке не обязательно иметь возможность сесть на автобус). Формально, заплатив \(a\) рублей Петя может добраться из \(i\) до \(j\), если \(s_t = \texttt{A}\) для всех \(i \le t < j\).
Если для двух перекрестков \(i\) и \(j\) на всех перекрестках \(i, i+1, \ldots, j-1\) есть троллейбусная остановка, то можно заплатить \(b\) рублей за билет на троллейбус, и доехать с \(i\)-й остановки до \(j\)-й (на \(j\)-й остановке не обязательно иметь возможность сесть на троллейбус). Формально, заплатив \(b\) рублей Петя может добраться из \(i\) до \(j\), если \(s_t = \texttt{B}\) для всех \(i \le t < j\).
Например, если \(s\)=«AABBBAB», \(a=4\) и \(b=3\), то Петя может:
- купить билет на автобус, чтобы добраться от \(1\) до \(3\),
- купить билет на троллейбус, чтобы добраться от \(3\) до \(6\),
- купить билет на автобус, чтобы добраться от \(6\) до \(7\).
Так, в общем ему нужно потратить \(4+3+4=11\) рублей. Обратите внимание, что остановка на последнем перекрестке (т.е. символ \(s_n\)) не влияет на итоговую стоимость.
Сейчас Петя находится на первом перекрестке, и он хочет попасть на \(n\)-й перекресток. После вечеринки у него осталось всего \(p\) рублей, и он хочет попасть домой. Он решил пройти несколько перекрестков пешком, а после этого доехать домой на общественном транспорте. Помогите ему выбрать ближайший перекресток \(i\) к первому так, чтобы ему хватило денег добраться с \(i\)-го перекрестка до \(n\)-го, используя лишь поездки на автобусах и троллейбусах.