#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; typedef pair Pl; const ll INF=1e18; int h, w; int gx, gy; int a[252][252]; ll dp[801][252][252]; ll d[51][252][252]; int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1}; int main() { cin>>h>>w; cin>>gx>>gy; gx--; gy--; for(int i=0; i>a[i][j]; } } for(int i=0; i<=800; i++){ for(int j=0; j=h || y1<0 || y1>=w) continue; dp[i+1][x1][y1]=min(dp[i][j][k]+a[x1][y1], dp[i+1][x1][y1]); } } } } for(int k=1; k<=50; k++){ for(int i=0; i, greater> que; que.push({d[k][gx][gy], {gx, gy}}); while(!que.empty()){ Pl p=que.top(); que.pop(); int x=p.second.first, y=p.second.second; if(d[k][x][y]=h || y1<0 || y1>=w) continue; if(d[k][x1][y1]>d[k][x][y]+k*k+a[x1][y1]){ d[k][x1][y1]=d[k][x][y]+k*k+a[x1][y1]; que.push({d[k][x1][y1], {x1, y1}}); } } } } int q; cin>>q; for(int i=0; i