Theo truyền thuyết xa xưa, có một năm khí hậu quá khô hạn vì không có đủ rồng để phun mưa. Chính vì vậy, Ngọc Hoàng đã mở một cuộc thi để tuyển chọn các con vật đủ khả năng cũng như phẩm chất hóa rồng để cứu nhân gian.

Thương xót trước tình cảnh những dòng sông cạn trơ đáy, cá tôm không còn chỗ để trú thân, người dân đói khổ, cây cối xác xơ, cá chép quyết tâm vượt qua cửa Vũ Môn để có thể hoá rồng, đem mưa tới cho nhân gian.

Để có thể đến được cửa Vũ Môn, cá chép phải bơi qua các thác nước cao lớn lên tận trời mây được mô tả giống như một ma trận kích thước ~n*m~. Nơi cá chép xuất phát là ô ~(1,1)~ và cổng vũ môn ở vị trí ~(n,m)~. Tại một thời điểm, cá chép chỉ chọn bơi sang trái, bơi sang phải hoặc bơi lên trên chứ không bao giờ bơi xuống. Sức lực cá chép cần bỏ ra để bơi từ ô ~(i,j)~ sang bên phải là ~r_{i,j}~, bơi sang trái là ~l_{i,j}~ và bơi lên trên là ~u_{i,j}~.

Cảm động trước sự quyết tâm và tấm lòng nhân hậu của cá chép, Ngọc Hoàng đã âm thầm giúp đỡ bằng cách tại mỗi hàng ~i~ của ma trận, Ngọc Hoàng sẽ thả xuống một hạt ngô thần tại vị trí ~p_i~. Khi cá chép bơi qua đây và ăn hạt ngô này, sức lực của cá chép sẽ được hồi phục lại ~c_i~.

Hãy giúp cá chép tính sức lực ít nhất mà cá chép cần bỏ ra để có thể đến được cửa Vũ Môn. Giá trị này có thể là một số âm.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~ (~2 \leq n,m \leq 1000~).

• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ~m~ số nguyên dương ~u_{i,1},u_{i,2},...,u_{i,m}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ lên trên (~0 \leq u_{i,j} \leq 10^9~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m-1~ số nguyên dương ~l_{i,2},l_{i,3},...,l_{i,m}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ sang trái (~0 \leq l_{i,j} \leq 10^9~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m-1~ số nguyên dương ~r_{i,1},r_{i,2},...,r_{i,m-1}~ là sức lực cá chép cần bỏ ra khi bơi từ ô ~(i,j)~ sang phải (~0 \leq r_{i,j} \leq 10^9~).

• ~n~ dòng cuối cùng, dòng thứ ~i~ gồm ~2~ số ~p_i~ và ~c_i~ (~1 \leq p_i \leq m~, ~0 \leq c_i \leq 10^9~).

Output

• In ra ~1~ số nguyên duy nhất là sức lực ít nhất cá chép cần bỏ ra để đến được cửa Vũ Môn.

Subtask

• ~10\%~ số test có ~2 \leq n,m \leq 5~.

• ~30\%~ số test khác có ~u_{i,j}=l_{i,j}=r_{i,j}=c_i=1~.

• ~20\%~ số test khác có ~c_i=0~.

• Còn lại không có điều kiện gì thêm.

Sample Input 1

2 3
1 1 1
1 1
1 1
1 1
1 1
2 1
1 1

Sample Output 1

2

Sample Input 2

2 2
1 2
2
4
2
1
2 7
1 3

Sample Output 2

-4

Sample Input 3

2 2
8 10
12
11
14
16
2 97
1 6

Sample Output 3

-73

Note

Ở ví dụ thứ hai, cá chép có thể có sức lực ban đầu là ~-4~:

• Từ ô ~(1,1)~ cá chép bơi sang phải ~1~ ô sang ô ~(1,2)~, mất ~2~ sức lực và ăn ngô hồi ~7~, sức lực hiện tại của cá chép là ~1~.

• Tiếp theo cá chép bơi sang trái về ô ~(1,1)~, mất ~2~ sức lực, hiện tại cá còn ~-1~ sức lực.

• Sau đó cá bơi lên ô ~(2,1)~, mất ~1~ sức lực và ăn ngô hồi ~3~, sức lực hiện tại của cá là ~1~. (Nếu cá bơi sang phải sang ô ~(1,2)~ một lần nữa, nó sẽ không được hồi ~7~ sức lực do mỗi ô chỉ có tối đa ~1~ hạt ngô được đặt, và cá đã ăn ngô ở đó từ trước).

• Cuối cùng cá bơi sang phải sang ô ~(2,2)~, là cửa Vũ Môn, mất ~1~ sức lực, còn ~0~ và vừa đủ để vượt cửa Vũ Môn.

Có thể chứng minh được cá không thể có sức lực ban đầu bé hơn ~-4~ để vượt cửa Vũ Môn.