Trò chơi điện tử

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ề là 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.

Để hướng dẫ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) vàD' (Down -- xuống dưới).

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ó thể hướng dẫn 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.

Input

Dữ liệu vào gồm một dòng duy nhất chứa chuỗi lệnh \(S\) (độ dài không vượt quá \(10^6\)).

Ràng buộc:

• Có \(60\%\) số test tương ứng với \(60\%\) số điểm: độ dài xâu không quá \(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.

Output

In ra một dòng duy nhất chứa một số nguyên \(t\) 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\).

Example 1

Input:

LURD

Output:

4

Example 2

Input:

LDLDURURL

Output:

8

Example 3

Input:

LLLLU

Output:

-1

Note

Ví dụ 1: Không phải xóa ký tự nào.

Ví dụ 2: Phải xóa đi \(01\) ký tự `L'.

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