Cupins vs Tamanduás: A Revanche

No tower defense “Cupins vs Tamanduás: A Revanche”, continuação do clássico “Tamanduás vs Cupins”, a premissa básica permanece a mesma: os tamanduás comem os cupins que tentam avançar para uma casa de madeira. Cada cupim tem uma massa, em miligramas, e o Tamanduá Bandeira, uma das torres aliadas, consegue consumir $M$ miligramas (mg) de cupim antes de ficar cheio e não conseguir comer mais cupins, deixando os demais atravessarem seu caminho.

Há três tipos de cupim no jogo: o Filhote, o Adulto e o Rei, cada um pesando $X$, $Y$ e $Z$ mg, respectivamente. Em uma wave (uma sequência ordenada de cupins que irão marchar para a casa de madeira), os cupins são consumidos na ordem que chegam aos tamanduás (que também estão organizados em uma fila), de acordo com os seguintes critérios:

Dadas as massas $X, Y, Z$ dos cupins, a capacidade de consumo $M$ do Tamanduá Bandeira, o número de inimigos $N$ e a ordem $S$ dos cupins na wave, determine o número mínimo de tamanduás que devem ser enfileirados para consumir toda a wave.

Entrada

A primeira linha da entrada contém os valores dos inteiros $X, Y$ e $Z$ ($1 \leq X, Y, Z \leq 10^5$), separados por um espaço em branco, que correspondem às massas, em miligramas, dos três tipos de cupim do jogo, conforme descrito anteriormente.

A segunda linha da entrada contém os inteiros $M$ e $N$ ($X, Y, Z \leq M \leq 10^5$, $1 \leq N \leq 2\times 10^5$), separados por um espaço em branco.

A terceira linha contém uma string $S$ de tamanho $N$, cujos caracteres ( F, A ou R) indicam o tipo de cupim (Filhote, Adulto e Rei, respectivamente) e a ordem que eles chegarão aos tamanduás (o cupim $S_i$ irá logo a frente do cupim $S_{i+1}$, com $i\in[1, N)$.

Saída

Imprima, em um linha, o número mínimo de tamanduás necessários para comer todos os cupins da wave.

Exemplo de entrada 1

3 8 10
20 3
AFR

Exemplo de saída 1

2

Explicação do exemplo 1: O tamanduá 1 come o cupim Adulto e, em seguida, o Filhote, totalizando uma massa consumida de 11 gramas. Deste modo, ele já não consegue ingerir o cupim Rei, cujo massa é de 10 gramas (pois só consegue comer mais 9 gramas), então o deixa para o segundo tamanduá, que o consome, finalizando a wave.

Exemplo de entrada 2

1 2 3
10 1
R

Exemplo de saída 2

1

Explicação do exemplo 2: Há apenas um cupim na wave, e um único tamanduá é necessário.

Exemplo de entrada 3

3 4 5
6 4
RFAF

Exemplo de saída 3

3

Explicação do exemplo 3: O tamanduá 1 consome o cupim Rei e o tamanduá 2 consome o Filhote que o sucede. O tamanduá 3 consumirá o Adulto (pois os tamanduás 1 e 2 podem ingerir apenas 1 ou 3 gramas, respectivamente). O último Filhote não pode ser consumido pelo tamanduá 1, mas o tamanduá 2 pode e o fará, finalizando a wave.

Exemplo de entrada 4

3 8 10
20 8
ARRFRRRF

Exemplo de saída 4

4