#1089. CAVERN - Chuyển hộp

Một hang động nằm dưới một núi đá, nối giữa thung lũng có điểm cao nhất với độ cao có cấu trúc không bằng phẳng có thể chia thành đoạn độ dài như nhau. Phía trên đoạn thứ là nhũ đá độ dài (tính từ điểm cao nhất của hang động). Phía dưới có những cấu trúc đá lồi lõm, ở đoạn thứ có độ cao . Người ta muốn thiết kế những khối hộp có mặt đáy vuông để chuyển hàng qua hang động. Vì yêu cầu đặc biệt, các khối hộp không được xoay, khi đưa vào chỉ được hoặc đẩy sang phải, hoặc di chuyển lên hoặc xuống.

Yêu cầu: Cho biết các độ cao và . Hãy xác định diện tích mặt bên lớn nhất của khối hộp có thể thiết kế.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên
• Dòng thứ hai chứa số nguyên không âm
• Dòng thứ ba chứa số nguyên không âm

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là kích thước tối đa khối hộp có thể sử dụng. Trường hợp không thể có đường qua hang, đưa ra .

Ví dụ:

Dữ liệu vào:

5 6
0 0 0 2 2 2  
2 0 0 0 0 0

Dữ liệu ra:

6

Giải thích:

Hình dạng của hang như sau:

...###.
...###.
.......
#......
#......

Giới hạn:

• số test có ;
• số test có ;
• số test khác có ;
• số test còn lại có .