Hamburgers

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A recipe string contains B, S, and C. Current stocks are $n_b,n_s,n_c$, unit prices are $p_b,p_s,p_c$, the store has unlimited supply, and you have $r$ money. Find the maximum number of hamburgers that can be produced.

Input

Input contains the recipe, stocks, prices, and money.

Output

Print the maximum number of hamburgers.

Subtasks

• Subtask 1 — 20%: $r\le10^5$.
• Subtask 2 — 30%: $r\le10^9$.
• Subtask 3 — 50%: recipe length $\le100$, stocks/prices $\le100$, $r\le10^{12}$.

Example

Input

BBBSSC
6 4 1
1 2 3
4

Output

2

Explanation

Two hamburgers require buying only one extra cheese unit.