Hamburger (Hamburgers)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một công thức hamburger là chuỗi gồm B, S, C, tương ứng bánh mì, xúc xích và phô mai. Mỗi ký tự cho biết một đơn vị nguyên liệu cần cho một hamburger.

Bạn đang có $n_b,n_s,n_c$ đơn vị ba nguyên liệu. Cửa hàng bán vô hạn với giá $p_b,p_s,p_c$ cho mỗi đơn vị. Bạn có $r$ tiền.

Hãy tìm số hamburger lớn nhất có thể làm. Không được chia nhỏ một đơn vị nguyên liệu.

Input

• Dòng 1: chuỗi công thức.
• Dòng 2: $n_b,n_s,n_c$.
• Dòng 3: $p_b,p_s,p_c$.
• Dòng 4: $r$.

Output

In số hamburger lớn nhất.

Subtask

• Subtask 1 — 20%: $r\le10^5$.
• Subtask 2 — 30%: $r\le10^9$.
• Subtask 3 — 50%: độ dài công thức $\le100$, $1\le n_b,n_s,n_c,p_b,p_s,p_c\le100$, $1\le r\le10^{12}$.

Ví dụ

Input

BBBSSC
6 4 1
1 2 3
4

Output

2

Giải thích

Hai hamburger cần $6$ bánh mì, $4$ xúc xích và $2$ phô mai. Ta chỉ thiếu một phô mai, mua với giá $3\le4$. Làm ba chiếc sẽ vượt ngân sách.