Làm bánh

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à t1 đồng, mỗi miếng xúc xích là t2 đồng và mỗi miếng pho mát là t3 đồ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.

Từ tệp văn bản HUMBERGER.INP 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 t1, t2, t3.
• Dòng 4: Chứa 1 số nguyên dương r.

Đưa ra tệp văn bản HUMBERGER.OUT 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.

• Các test tương ứng với 50% có $m, n, k, t1, t2, t3 \le 10^3; r \le 10^{12}$.
• Các test tương ứng với 50% có $m, n, k, t1, t2, t3 \le 10^9; r \le 10^{12}$.

Chú ý: Các số trên cùng một dòng tệp dữ liệu vào hoặc kết quả cách nhau ít nhất một dấu cách.