Có các thẻ ghi I ở mặt trước và O ở mặt sau. Ban đầu xếp lần lượt \(A\) thẻ ngửa, \(B\) thẻ úp, \(C\) thẻ ngửa, \(D\) thẻ úp, rồi \(E\) thẻ ngửa.

Có \(N\) loại thao tác. Loại \(i\) lật mọi thẻ từ vị trí \(L_i\) đến \(R_i\), tốn \(R_i-L_i+1\) giây. Phải thực hiện ít nhất một thao tác; được chọn thứ tự tùy ý và dùng một loại nhiều lần. Hãy tìm thời gian nhỏ nhất để mọi thẻ đều ngửa, hoặc xác định rằng không thể.

Dữ liệu vào

• Dòng 1: \(A,B,C,D,E\).
• Dòng 2: \(N\).
• \(N\) dòng tiếp: \(L_i,R_i\).

Dữ liệu ra

In thời gian nhỏ nhất, hoặc -1 nếu không thể thành công.

Ràng buộc

Phân nhóm

• Nhóm 1 (15 điểm): \(N\le10\).
• Nhóm 2 (50 điểm): \(A,B,C,D,E\le50\).
• Nhóm 3 (35 điểm): không có ràng buộc bổ sung.

Ví dụ

1 2 3 4 5
3
2 3
2 6
4 10

12

1 1 1 1 1
1
1 1

-1