Trong cơ chế mở khóa của điện thoại, mỗi lần bật máy sẽ xuất hiện một lưới ô vuông kích thước ~2 \times 3~ (2 hàng, 3 cột). Ta coi các đỉnh là các giao điểm của các đường kẻ, nên có ~3 \times 4 = 12~ đỉnh, và các cạnh là các đoạn nối hai đỉnh kề nhau (ngang/dọc). Trên mỗi cạnh có ghi một số nguyên không âm — số đồng tiền vàng hiện có trên cạnh đó.

Người dùng có thể bắt đầu từ bất kỳ đỉnh nào, sau đó di chuyển dọc theo các cạnh theo quy tắc:

• Chỉ được đi qua một cạnh nếu trên cạnh đó còn ít nhất 1 đồng tiền.

• Nếu đi qua một cạnh đang có ~t~ đồng tiền thì:

  • Người dùng nhặt được ~\lceil t/2 \rceil~ đồng.
  • Trên cạnh đó còn lại ~\lfloor t/2 \rfloor~ đồng.
• Khi đến một đỉnh mà tất cả các cạnh kề với nó đều có ~0~ đồng, quá trình di chuyển kết thúc.

Steve muốn biết tổng số đồng tiền tối đa có thể nhặt được (chọn điểm bắt đầu và đường đi tối ưu) để nhập vào điện thoại.

Hình minh họa: http://chuyenvinhphuc.edu.vn/static/imgs/00103.png

Yêu cầu

Tính giá trị lớn nhất của tổng số đồng tiền có thể thu được theo quy tắc trên trên lưới ~2 \times 3~.

Dữ liệu

• Các dòng ~1~, ~3~, ~5~: mỗi dòng chứa ~3~ số nguyên, lần lượt là số đồng tiền trên các cạnh ngang từ trái sang phải.
• Các dòng ~2~, ~4~: mỗi dòng chứa ~4~ số nguyên, lần lượt là số đồng tiền trên các cạnh dọc từ trái sang phải.

Diễn giải theo hệ tọa độ đỉnh ~ (r, c) ~ với ~r \in {1,2,3}~, ~c \in {1,2,3,4}~:

• Dòng ~1~: các cạnh ngang nối ~(1,1)-(1,2)~, ~(1,2)-(1,3)~, ~(1,3)-(1,4)~.
• Dòng ~3~: các cạnh ngang nối ~(2,1)-(2,2)~, ~(2,2)-(2,3)~, ~(2,3)-(2,4)~.
• Dòng ~5~: các cạnh ngang nối ~(3,1)-(3,2)~, ~(3,2)-(3,3)~, ~(3,3)-(3,4)~.
• Dòng ~2~: các cạnh dọc nối ~(1,c)-(2,c)~ với ~c=1..4~.
• Dòng ~4~: các cạnh dọc nối ~(2,c)-(3,c)~ với ~c=1..4~.

Giới hạn:

• Mọi giá trị trên cạnh là số nguyên ~t~ với ~0 \le t \le 10^9~.

Kết quả

Ghi ra một số nguyên — tổng số đồng tiền tối đa Steve có thể thu được.

Ví dụ

Ví dụ 1

Input

1 2 3
4 5 6 7
8 9 10
11 12 13 14
15 16 17

Output

150

Giải thích

Ví dụ 1

Có một cách chọn điểm bắt đầu và đường đi sao cho tổng số tiền nhặt được là lớn nhất, và giá trị tối đa đó bằng ~150~.

Ràng buộc và chấm điểm

Ràng buộc

• Dữ liệu gồm đúng ~17~ giá trị ứng với ~17~ cạnh của lưới ~2 \times 3~.
• ~0 \le t \le 10^9~ cho mọi cạnh.