Jessie là một thợ săn quái vật trong một trò chơi điện tử mới ra mắt. Trò chơi gồm nhiều màn chơi, trong đó mỗi màn có dạng một dãy các ô được đánh số lần lượt \(1, 2, 3, \dots\). Jessie cần xuất phát từ ô \(1\) và đi qua từng ô đến ô cuối cùng để hoàn thành màn chơi. Màn chơi hiện tại của Jessie gồm có \(N\) ô, mỗi ô thuộc một trong 4 loại sau:

• Ô trống - Jessie có thể đi qua ô này một cách bình thường;
• Ô hồi thể lực - khi đi ngang ô hồi thể lực, thể lực của Jessie được tăng \(1\) đơn vị;
• Ô hồi máu - khi đi ngang ô hồi máu, máu của Jessie được tăng \(1\) đơn vị;
• Ô quái vật - khi đi ngang ô có quái vật, Jessie có hai lựa chọn là tiêu diệt tên quái vật đó đồng thời mất \(1\) đơn vị thể lực, hoặc chịu đòn và mất \(1\) đơn vị máu.

Bắt đầu màn chơi, Jessie có điểm thể lực là \(P\) và máu là \(H\). Do thể lực là một tài nguyên hiếm trong trò chơi, bạn hãy giúp Jessie xác định số lượng quái vật \bf{ít nhất} cần tiêu diệt để có thể hoàn thành màn chơi này.

Trong mọi thời điểm, cần đảm bảo cả thể lực lẫn máu lớn hơn \(0\).

Input

• Dòng đầu tiên chứa ba số nguyên \(N, P, H\) \((1 \le N, P, H \le 2 \times 10^5)\) - lần lượt là số ô trong màn chơi, lượng thể lực và máu của nhân vật vào đầu màn chơi.
• Dòng tiếp theo chứa một chuỗi độ dài \(N\) chỉ gồm các kí tự # - ô trống, P - ô hồi thể lực, H - ô hồi máu, hoặc M - ô có quái vật.

Output

Gồm một dòng duy nhất in ra số quái vật ít nhất cần tiêu diệt để có thể qua màn chơi tiếp theo. Nếu không thể vượt qua màn chơi với lượng máu và thể lực hiện tại, in ra -1.

Scoring

• Subtask \(1\) \((20\%)\): \(1 \le N, P, H \le 20\);
• Subtask \(2\) \((32\%)\): \(1 \le N, P, H \le 200\);
• Subtask \(3\) \((18\%)\): Không có ô hồi máu hay hồi sức xuất hiện trong màn chơi;
• Subtask \(4\) \((30\%)\): Không có ràng buộc gì thêm;

Example

5 1 2
#PMMH

1

5 2 2
#M#MM

-1