Khoa là một người cô đơn và không có bạn, vì thế anh ấy thường tự chơi bi một mình. Hôm nay, anh ấy lại sáng chế ra một trò chơi khác, với nội dung như sau:
Có ô đất được xếp thành một hàng ngang đánh số thứ tự từ đến . Ban đầu, Khoa sẽ chọn ô đất phân biệt và , và đặt vào mỗi ô đất một viên bi. Ở mỗi lượt chơi, Khoa có thể thực hiện các thao tác sau:
Di chuyển một trong hai viên bi, qua trái hoặc qua phải đơn vị, với chi phí là ;
Di chuyển cả hai viên bi, qua trái hoặc qua phải đơn vị, với chi phí là .
Sau mỗi bước di chuyển, Khoa phải bảo đảm rằng viên bi không được chứa trong cùng một ô đất. Khoa đánh dấu vị trí hai ô đích đến phân biệt là và . Cuối cùng, Khoa cần tìm chi phí ít nhất để di chuyển viên bi đến ô , sao cho cuối cùng, trong mỗi ô đều có bi.
Lưu ý rằng viên bi ở ô không bắt buộc phải kết thúc ở , và bi ở cũng không bắt buộc kết thúc ở .
Dữ liệu:
Dòng đầu tiên gồm ba số nguyên ;
Dòng thứ hai gồm bốn số nguyên .
Kết quả:
In ra chi phí ít nhất để di chuyển hai viên bi từ ô đến ô .
Ví dụ:
Dữ liệu:
4 1 1
1 2 3 4
Kết quả:
2
Dữ liệu:
4 1 3
1 2 3 4
Kết quả:
4
Dữ liệu:
6 2 3
3 4 6 1
Kết quả:
8
Giải thích:
Ở ví dụ , Khoa di chuyển cả hai viên bi, qua phải hai đơn vị, với chi phí là ;
• Ở ví dụ , Khoa di chuyển viên bi ở vị trí , qua phải hai đơn vị, và di chuyển viên bi ở vị trí , qua phải hai đơn vị. Vậy tổng chi phí là ;
Ở ví dụ , Khoa di chuyển viên bi ở vị trí , qua trái hai đơn vị, và di chuyển viên bi ở vị trí , qua phải hai đơn vị. Vậy tổng chi phí là .
