B'After a long party Petya decided to return home, but he turned out to be at the opposite end of the town from his home. There are n crossroads in the line in the town, and there is either the bus or the tram station at each crossroad. The crossroads are represented as a string s of length n , where s_i = texttt{A} , if there is a bus station at i -th crossroad, and s_i = texttt{B} , if there is a tram station at i -th crossroad. Currently Petya is at the first crossroad (which corresponds to s_1 ) and his goal is to get to the last crossroad (which corresponds to s_n ). If for two crossroads i and j for all crossroads i, i+1, ldots, j-1 there is a bus station, one can pay a roubles for the bus ticket, and go from i -th crossroad to the j -th crossroad by the bus (it is not necessary to have a bus station at the j -th crossroad). Formally, paying a roubles Petya can go from i to j if s_t = texttt{A} for all i <= t < j . If for two crossroads i and j for all crossroads i, i+1, ldots, j-1 there is a tram station, one can pay b roubles for the tram ticket, and go from i -th crossroad to the j -th crossroad by the tram (it is not necessary to have a tram station at the j -th crossroad). Formally, paying b roubles Petya can go from i to j if s_t = texttt{B} for all i <= t < j . For example, if s ="AABBBAB", a=4 and b=3 then Petya needs: Thus, in total he needs to spend 4+3+4=11 roubles. Please note that the type of the stop at the last crossroad (i.e. the character s_n ) does not affect the final expense. Now Petya is at the first crossroad, and he wants to get to the n -th crossroad. After the party he has left with p roubles. He 's decided to go to some station on foot, and then go to home using only public transport. Help him to choo'...