Sản lượng tối đa theo công thức nguyên liệu

Bối cảnh và bài toán

Một xưởng sản xuất một sản phẩm theo công thức là chuỗi ký tự B, S, C; mỗi ký tự biểu thị cần một đơn vị của loại nguyên liệu tương ứng. Xưởng có tồn kho ban đầu, có thể mua thêm không giới hạn theo đơn giá cố định và có ngân sách r.

Yêu cầu

Tìm số sản phẩm tối đa có thể sản xuất.

Input

• Dòng 1: chuỗi công thức.
• Dòng 2: tồn kho nB nS nC.
• Dòng 3: đơn giá pB pS pC.
• Dòng 4: ngân sách r.

Output

In số sản phẩm tối đa.

Ràng buộc

• 1 <= |recipe| <= 100
• recipe chỉ gồm B, S, C
• 1 <= nB, nS, nC <= 100
• 1 <= pB, pS, pC <= 100
• 1 <= r <= 10^12

Chấm điểm

Ví dụ 1

Input

BBBSSC
6 4 1
1 2 3
4

Output

2

Giải thích. Công thức cần 3 B, 2 S, 1 C mỗi sản phẩm; với tồn kho và 4 đơn vị ngân sách chỉ làm tối đa 2 sản phẩm.

Ví dụ 2

Input

BSC
1 1 1
1 1 3
1000000000000

Output

200000000001

Giải thích. Ngân sách rất lớn khiến đáp án vượt xa 32-bit, vì vậy cận và phép tính chi phí phải dùng kiểu đủ rộng.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 371C — Hamburgers.

Tham khảo: https://codeforces.com/problemset/problem/371/C