A Policarpo le encantan las hamburguesas que prepara con sus propias manos. Para él solo hay tres ingredientes decentes: pan, salchicha y queso. Escribe la receta de su hamburguesa favorita "Le Hamburger de Polycarpus" como una cadena de caracteres formada por 'P' (pan), 'S' (salchicha) y 'Q' (queso). Los ingredientes van de abajo hacia arriba; por ejemplo, la receta PSQPS representa una hamburguesa con, de abajo hacia arriba, pan, salchicha, queso, pan y salchicha.

En su cocina tiene \(n_p\) piezas de pan, \(n_s\) piezas de salchicha y \(n_q\) piezas de queso. Además, en la tienda cercana hay cantidades ilimitadas de cada ingrediente, con precios \(p_p\) (pan), \(p_s\) (salchicha) y \(p_q\) (queso) por unidad. Policarpo dispone de \(r\) rublos para gastar.

¿Cuál es el número máximo de hamburguesas que puede preparar? No puede cortar ni fraccionar piezas, y los precios son por pieza entera.

Entrada

1. Una línea con la cadena no vacía de la receta (longitud \(≤ 100\)), compuesta solo por 'P', 'S' y 'Q'.
2. Una línea con tres enteros \(n_p\), \(n_s\), \(n_q\) \((1 ≤ n_p, n_s, n_q ≤ 100)\): las unidades de pan, salchicha y queso que tiene.
3. Una línea con tres enteros \(p_p\), \(p_s\), \(p_q\) \((1 ≤ p_p, p_s, p_q ≤ 100)\): los precios en rublos de cada unidad de pan, salchicha y queso.
4. Una línea con un entero \(r\) \((1 ≤ r ≤ 10^{12})\): los rublos disponibles.

Salida

Imprime un entero: el número máximo de hamburguesas que puede preparar. Si no puede preparar ninguna, imprime 0.

Ejemplos

Entrada

PPPSSQ
6 4 1
1 2 3
4

Salida

2

Entrada

PPQ
1 10 1
1 10 1
21

Salida

7

Entrada

PSQ
1 1 1
1 1 3
1000000000000

Salida

200000000001