Subtask 1:

Dễ nhận thấy để đường đi tối ưu, vì ~u_{i,j}~, ~l_{i,j}~, và ~r_{i,j}~ lớn hơn hoặc băng ~0~ với mọi ~i,j~, nên với mọi ô cá chép được đi tối đa không quá ~2~ lân. Vì vậy, với mỗi hàng, ta có thể tìm đỉnh đầu, đỉnh giữa (đỉnh quay đầu để đi lại đến đỉnh tối ưu) và đỉnh cuối bằng thuật toán quay lui.

Subtask 2:

Vì ~u_{i, j}~ = ~l_{i, j}~ = ~r_{i, j}~ = ~1~ và ~c_i = 1~ với mọi ~1 \leq i \leq n~, nên ta thấy ta không bao giờ đi qua một ô nhiều hơn ~2~ lần. Mọi cạnh từ nối đến các ô ~(i, p_i)~ đều có trọng số bằng ~0~ do ta đi vào ô này và ăn hạt ngô thần ngay lập tức nên không mất chút sức lực nào, các cạnh còn lại có trọng số bằng ~1~. Ta dùng thuật toán 0-1 BFS để tìm đường đi ngắn nhất từ ô ~(1, 1)~ đến ô ~(n, m)~.

Subtask 3:

Vì ~c_i = 0~ với mọi ~1 \leq i \leq n~ nên đồ thị chỉ tồn tại cạnh có trọng số không âm từ mọi đỉnh ~(i, j)~ sang các đỉnh kề nó. Ta dùng thuật toán dijkstra để tìm đường đi ngắn nhất từ đỉnh ~(1, 1)~ đến đỉnh ~(n, m)~.

Subtask 4:

Ta gọi ~dp_{i, j}~ là sức lực ít nhất cá chép cần bỏ ra đề có thể đi từ ô ~(1, 1)~ đến ô ~(i, j)~.

Ta nhận thấy rằng đây là đồ thị tồn tại cạnh có trọng số âm từ các ô có toạ độ ~(i, p_i)~ đến chính nó. Tuy nhiên để có thể đến được các ô ở ~i~ bắt buộc phải đi qua hàng ~i-1~, nên thay vì dijkstra trên toàn bộ đồ thị ~n~ x ~m~ đỉnh, vỡi mỗi ô của hàng ~i~, ban đầu ta gán ~dp_{i, j}~ = ~dp_{i-1, j}~ + ~u_{i-1, j}~, sau đó ta dùng các giá trị này để có thể dijkstra trên toàn bộ hàng ~i~.

Để có thể dijkstra trên các ô của hàng ~i~, vì số lượng hạt ngô thần trên mỗi hàng chỉ có ~1~, nên trước hết ta giả sử các chép sẽ đi tới và ăn hạt ngô này để tránh trường hợp ăn hai lần. Ta có hai biến:

• ~tmp1~ = ~min~(~dp_{i, j}~ + ~r_{i, j}~ + ... + ~r_{i, p_i - 1}~) với ~(1 \leq j \leq p_i)~.

• ~tmp2~ = ~min~(~dp_{i, j}~ + ~l_{i, j}~ + ... + ~l_{i, p_i + 1}~) với ~(p_i \leq j \leq m)~.

~dp_{i, p_i}~ = ~min~(~dp_{i, p_i}~, ~min~(~tmp1~, ~tmp2~) - ~c_i~).

Vì đi một lần nhiều bước sang trái hoặc sang phải cũng giống đi nhiều lần một bước, và giờ đã không cần quan tâm đến hạt ngô thần nữa, vì vậy ta dijkstra, mỗi lần chọn ô tốn ít sức nhất của hàng ~i~ và cập nhật cho ô ~i-1~ và ~i+1~ nếu có.

Code mẫu

/*
Oh my god is that soda
*/
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for (ll i=m;i<=n;++i)
#define reb(i,m,n) for (ll i=m;i>=n;--i)
#define rv(i,vt) for (auto i:vt)
#define ii pair<ll,ll>
#define vi vector<int>
#define F first
#define S second
#define pb push_back
using namespace std;
const ll N=2e5+5,mod=1e9+7;
ll n,m,c[1005][1005],u[1005][1005],l[1005][1005],r[1005][1005],cost[1005][1005],mx[2005];
void solo()
{
    cin>>n>>m;
    rep(i,1,n)
    rep(j,1,m) u[i][j]=l[i][j]=r[i][j]=1e18,c[i][j]=0;
    rep(i,1,n-1)
    rep(j,1,m) cin>>u[i][j];
    rep(i,1,n)
    rep(j,2,m) cin>>l[i][j];
    rep(i,1,n)
    rep(j,1,m-1) cin>>r[i][j];
    rep(i,1,n){
        ll j,w;
        cin>>j>>w;
        c[i][j]=w;
    }
    rep(i,1,n){
        priority_queue<ii,vector<ii>,greater<ii>> pq;
        rep(j,1,2*m) mx[j]=1e18;
        ll mi=m;
        if (i==1) mi=1;
        rep(j,1,min(mi,m)) if (c[i][j]==0) 
        {
            pq.push({cost[i][j],j});
            mx[j]=min(mx[j],cost[i][j]);
        }
        else 
        {
            pq.push({cost[i][j]-c[i][j],j+m});
            mx[j+m]=min(mx[j+m],cost[i][j]-c[i][j]);
        }
        ll cnt=0;
        while (!pq.empty()){
            auto [w,v]=pq.top();
            pq.pop();
            if (mx[v]!=w) continue;
            bool ok=0;
            if (v>m) v-=m,ok=1;
            if (l[i][v]!=1e18){
                ll v1=v-1+ok*m;
                if (c[i][v-1]!=0) v1+=m;
                if (v1<=2*m)
                if (mx[v1]>(-c[i][v-1]+l[i][v]+w)){
                    mx[v1]=-c[i][v-1]+l[i][v]+w;
                    pq.push({mx[v1],v1});
                }
            }
            if (r[i][v]!=1e18){
                ll v1=v+1+ok*m;
                if (c[i][v+1]!=0) v1+=m;
                if (v1<=2*m)
                if (mx[v1]>(-c[i][v+1]+r[i][v]+w)){
                    mx[v1]=-c[i][v+1]+r[i][v]+w;
                    pq.push({mx[v1],v1});
                }
            }
        }
        rep(j,1,m) cost[i][j]=mx[j];
        rep(j,m+1,2*m) cost[i][j-m]=min(cost[i][j-m],mx[j]),cost[i+1][j-m]=cost[i][j-m]+u[i][j-m];
    }
    cout<<cost[n][m];
}
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ll t=1;
   //cin>>t;
   while (t--){
       solo();
       cout<<endl;
   }
}