Tamanduás vs. Cupins

No tower defense Tamanduás vs Cupins, 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), da seguinte forma:

1. um tamanduá come um cupim imediatamente, de modo que ele consegue comer um cupim antes que o próximo cupim da sequência chegue a ele;
2. se o tamanduá puder comer o cupim, ele o comerá;
3. um tamanduá não pode comer apenas parte de um cupim: se ele não conseguir consumir o cupim inteiro, ele deixará o mesmo passar para o próximo tamanduá.

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 de um caso de teste contém os valores dos inteiros $X, Y, Z$ $(1 \leq X, Y, Z \leq 1.000)$, 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$ $(\max\lbrace X, Y, Z\rbrace \leq M \leq 2.000, 1 \leq N \leq 2\times 10^3)$, separados por um espaço em branco.

A terceira linha contém uma string $S$ de tamanho $N$, cujos caracteres ($F, A, 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 $T$ 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: 2 tamanduás são suficientes: o primeiro come os dois primeiros cupins, num total de 11 mg. Ele não consegue comer o terceiro (pois só tem espaço para mais 9 mg), de modo que o terceiro cupim é comido pelo segundo tamanduá.

Exemplo de entrada 2

1 2 3
10 1
R

Exemplo de saída 2

1

Explicação do exemplo 2: Um único tamanduá consegue comer os 3 cupins, uma vez que a massa total deles (6 mg) é inferior a capacidade do tamanduá (10 mg).

Exemplo de entrada 3

3 4 5
6 4
RFAF

Exemplo de saída 3

3

Explicação do exemplo 3: São necessários 3 tamanduás. Veja o diagrama abaixo

+++++++++++++++++++++++
Cupim       Tamanduás
+++++++++++++++++++++++
            6   6   6
R           1   6   6
F           1   3   6
A           1   3   2
F           1   0   1
+++++++++++++++++++++++

Exemplo de entrada 4

3 8 10
20 8
ARRFRRRF

Exemplo de saída 4

4

Explicação do exemplo 4: 4 tamanduás são suficientes para consumir todos os cupins.