Nhân dịp con trai đạt kết quả cao trong kì thi học sinh giỏi, Ông Jasson đã nghĩ ra món quà đặc biệt tặng con trai. Đó là chiếc bánh do chính tay ông tự làm, thành phần của bánh là bánh mì (B), xúc xích (X) và pho mát (P) tạo thành từng lớp. Các lớp bánh đi từ dưới lên trên, ví dụ như công thức “BXPBX” là miếng bánh gồm bánh mì, xúc xích, pho mát, bánh mì và xúc xích. Ông Jasson đang có ~ m ~ miếng bánh mì, ~ n ~ miếng xúc xích và ~ k ~ miếng pho mát. Giá mua thêm mỗi thành phần như sau: mỗi miếng bánh mì là ~ t_1 ~ đồng, mỗi miếng xúc xích là ~ t_2 ~ đồng và mỗi miếng pho mát là ~ t_3 ~ đồng.

Yêu cầu: Hãy xác định số bánh ông có thể làm được nhiều nhất với chi phí mua thêm các thành phần không quá ~ r ~ đồng.

Dữ liệu vào: Gồm nhiều bộ dữ liệu (số bộ dữ liệu không quá ~ 10^7 ~), mỗi bộ dữ liệu cho trên một nhóm 4 dòng:

• Dòng 1: Chứa một xâu (độ dài lớn hơn 0 và không quá 100) chỉ chứa các ký tự ‘B’, ‘X’, ‘P’ thể hiện công thức làm một chiếc bánh của Jasson.
• Dòng 2: Chứa ba số tự nhiên ~ m, n, k ~.
• Dòng 3: Chứa ba số nguyên dương ~ t_1, t_2, t_3 ~.
• Dòng 4: Chứa 1 số nguyên dương ~ r ~.

Kết quả:

• Đưa ra tương ứng với mỗi bộ dữ liệu là số lượng bánh tối đa ông có thể được làm.

Ví dụ:

Input

BBBXXP
6 4 1
1 2 3
4
BBP
1 10 1
1 10 1
21 

Output

2
7 

Giải thích: có 4 đồng sẽ mua 1 miếng pho mát hết 3 đồng. Tổng cộng có 6 miếng bánh mỳ, 4 miếng xúc xích, và 2 miếng pho mát. Nên có thể làm được 2 chiếc bánh.

Ràng buộc:

• Các test tương ứng với 50% có ~ m, n, k, t_1, t_2, t_3≤10^3; r≤10^{12}~
• Các test tương ứng với 50% có ~ m, n, k, t_1, t_2, t_3≤10^9; r≤ 10^{12} ~