A Mộng muốn làm bánh dorayaki. Mỗi chiếc bánh được làm theo cùng một công thức, cho dưới dạng một chuỗi gồm các ký tự b và f: mỗi ký tự b là cần $1$ phần nguyên liệu loại b, mỗi ký tự f là cần $1$ phần nguyên liệu loại f.

Trong nhà A Mộng đang có sẵn $a$ phần nguyên liệu b và $b$ phần nguyên liệu f. Ngoài cửa hàng, mỗi phần nguyên liệu b giá $c$ đồng, mỗi phần nguyên liệu f giá $d$ đồng, số lượng không giới hạn. A Mộng có $n$ đồng.

Hỏi A Mộng làm được nhiều nhất bao nhiêu chiếc bánh dorayaki?

Dữ liệu vào

Dòng đầu tiên gồm một số nguyên $n$ là số tiền A Mộng có.

Dòng thứ hai là chuỗi công thức, chỉ gồm các ký tự b và f.

Dòng thứ ba gồm bốn số nguyên $a, b, c, d$.

Dữ liệu ra

In ra một số nguyên là số bánh nhiều nhất làm được.

Ví dụ

Input

15
fbbfb
0 0 1 1

Output

3

Ghi chú

Giải thích ví dụ

Mỗi chiếc bánh cần $3$ phần b và $2$ phần f, tức tốn $3 \times 1 + 2 \times 1 = 5$ đồng khi phải mua hết. Với $15$ đồng làm được $3$ chiếc.

Phạm vi dữ liệu

• $0 \le n \le 10^{11}$
• Chuỗi công thức dài từ $1$ đến $100$ ký tự
• $0 \le a, b \le 100$, $1 \le c, d \le 100$