An sử dụng một ứng dụng nhắn tin và muốn biết bạn của mình, Bình, có những khoảng thời gian online liên tục dài nhất là bao lâu trong một ngày. Hệ thống ghi lại trạng thái của Bình mỗi phút trong suốt ~T~ phút của một ngày. Trạng thái có thể là một trong ba loại: "ONLINE", "IDLE" (không hoạt động), hoặc "OFFLINE".

Một "chuỗi online" được định nghĩa là một khoảng thời gian liên tục mà trạng thái của Bình là "ONLINE".

Yêu cầu: Cho chuỗi các trạng thái của Bình trong ~T~ phút, hãy tìm độ dài của chuỗi online liên tục dài nhất. Nếu Bình không online phút nào, kết quả là 0.

Input

• Dòng đầu tiên chứa số tự nhiên ~T~ (~1 \le T \le 1440~), tổng số phút theo dõi trong ngày.
• ~T~ dòng tiếp theo, mỗi dòng chứa một xâu ký tự là trạng thái của Bình tại phút tương ứng: "ONLINE", "IDLE", hoặc "OFFLINE".

Output

• Một số nguyên duy nhất là độ dài của chuỗi online liên tục dài nhất.

Sample Input 1

10
ONLINE
ONLINE
IDLE
ONLINE
ONLINE
ONLINE
OFFLINE
ONLINE
ONLINE
IDLE

Sample Output 1

3

Một chiếc xe điện bắt đầu hành trình từ điểm 0 km với pin đầy, dung lượng pin tối đa là ~P_{max}~ đơn vị. Mỗi km di chuyển tiêu tốn 1 đơn vị pin.

Trên quãng đường có ~N~ trạm sạc. Trạm thứ ~i~ (với ~i=1, 2, \dots, N~) nằm ở vị trí ~D_i~ km tính từ điểm xuất phát và tại đó xe có thể sạc đầy pin (lên ~P_{max}~) ngay lập tức.

Xe không thể di chuyển nếu pin không đủ cho 1 km tiếp theo. Đích đến là thành phố ở vị trí ~D_{target}~ km.

Yêu cầu: Tìm số lần sạc ít nhất để xe có thể đi từ điểm 0 đến ~D_{target}~. Nếu không thể đến đích, ghi ra -1.

Input

• Dòng đầu tiên: ba số tự nhiên ~N, P_{max}, D_{target}~ (~0 \le N \le 1000, 1 \le P_{max} \le 10^9, 1 \le D_{target} \le 10^9~).
• ~N~ dòng tiếp theo: mỗi dòng chứa một số nguyên ~D_i~ (~1 \le D_i < D_{target}~).

Output

• Một số nguyên là số lần sạc ít nhất, hoặc -1 nếu không thể đến đích.

Sample Input 1

3 175 350
80
180
280

Sample Output 1

2

Một trò chơi xếp chữ trên điện thoại, người chơi có một chuỗi ký tự ~s~. Mỗi lượt chơi được phép xóa một ký tự bất kỳ. Trò chơi kết thúc khi chuỗi còn lại là palindrome (đọc xuôi ngược như nhau). Ví dụ: chuỗi "aca" hoặc "racecar" là chuỗi palindrome.

Yêu cầu: Tìm số lượt chơi ít nhất để chuỗi ban đầu trở thành palindrome.

Input

• Chuỗi ký tự ~s~ (~1 \le \text{độ dài} \le 2000~, chỉ gồm chữ thường).

Output

• Số lượt chơi ít nhất.

Sample Input 1

abcca

Sample Output 1

1

Trong một hệ thống blockchain, thợ đào chọn các giao dịch đang chờ (giả sử có ~N~ giao dịch) để đưa vào một khối mới. Mỗi giao dịch thứ ~i~ có phí ~F_i~ và kích thước ~S_i~ (với ~i=1, 2, \dots, N~) và ~F_i, S_i~ là các số nguyên dương. Khối có kích thước tối đa là ~S_{max}~ (~S_{max}~ là số nguyên dương). Thợ đào muốn tối đa tổng phí ~F_i~ sao cho tổng kích thước ~S_i~ không vượt ~S_{max}~.

Giả sử rằng có ~D~ ràng buộc phụ thuộc: nếu giao dịch A được chọn thì giao dịch B cũng phải được chọn. Các phụ thuộc này không tạo thành chu trình.

Yêu cầu: Tìm tổng phí giao dịch lớn nhất.

Input

• Dòng 1: ~N, S_{max}~ (~1 \le N \le 50, 1 \le S_{max} \le 1000~).
• ~N~ dòng tiếp theo: ~F_i, S_i~ (~1 \le F_i, S_i \le 1000~) cho giao dịch ~i~.
• Dòng tiếp: ~D~ (~0 \le D \le \frac{N(N-1)}{2}~).
• ~D~ dòng tiếp (nếu ~D>0~): ~A, B~ (thể hiện cho ràng buộc nếu chọn A phải chọn B, trong đó ~A, B \in \{1, 2, \dots, N\}~).

Output

• Tổng phí lớn nhất.

Sample Input 1

3 10
10 5
7 4
3 3
1
1 2

Sample Output 1

17