Trong trò chơi điện tử có tên Zentric, nhân vật được điều khiển di chuyển trên một lưới (giả sử số ô không hạn chế).

Khởi đầu trò chơi, nhân vật được đặt tại một ô bất kỳ. Tại mỗi bước, nhân vật có thể di chuyển đến ô liền kề theo một trong số các ô bên trái, bên phải, phía trên, phía dưới của ô hiện tại.

Để điều khiển nhân vật di chuyển, cần một chuỗi lệnh S gồm các ký tự:

'L'(Left) – sang trái

'R' (Right) – sang phải

'U' (Up) – lên trên

'D' (Down) – xuống dưới

Sau cho trước chuỗi lệnh ~S~, để hoàn thành màn chơi, bạn cần chỉnh sửa lại chuỗi lệnh S sao cho các bước theo hướng đó nhân vật di chuyển qua các ô, mỗi ô được phép đi qua không quá một lần và phải trở về đúng ô xuất phát. Việc chỉnh sửa lại chuỗi lệnh S có thể được thực hiện bằng cách:

Xóa đi một số ký tự (có thể không xóa ký tự nào) trong chuỗi lệnh ~S~;

Thay đổi vị trí các ký tự trong chuỗi lệnh ~S~ theo ý muốn.

Yêu cầu: Hãy xác định độ dài lớn nhất của chuỗi lệnh ~S~ sau khi thực hiện việc chỉnh sửa.

Dữ liệu vào:

• Dòng 1: Chứa chuỗi lệnh S (độ dài không vượt quá ~10^6~).

Kết quả:

• Dòng 1: Ghi một số nguyên là kết quả của bài toán. Trường hợp không thể chỉnh sửa chuỗi lệnh S để hoàn thành màn chơi thì ghi -1.

Ví dụ:

Input

LURD

Output

4

Input2

LDLDURURL

Output2

8

Input3

LLLLU

Output3

-1

Giải thích:

• Với LURD: Không phải xóa ký tự nào.

• Với LDLDURURL: Phải xóa đi 01 ký tự 'L'.

• Với LLLLU: Không có phương án chỉnh sửa chuỗi để hoàn thành màn chơi.

Ràng buộc:

• Có 60% số test tương ứng với 60% số điểm có độ dài xâu không qáu 255 ký tự.

• Có 40% số test tương ứng với 40% số điểm không có ràng buộc gì thêm.