#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    LL a[n], b[n];

    loop(i,0,n) cin>>a[i];
    loop(i,0,n) cin>>b[i];

    LL mx = 0, ans = 0;

    loop(i,0,n)
    {
        mx = max(mx, a[i]);
        b[i] *= mx;

        ans = max(ans, b[i]);

        cout<<ans<<'\n';
    }

    return 0;
}

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T>>;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}



//head



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int r, c;
  cin >> r >> c;
  vector<vector<P>> G(r*c*2);
  auto num = [&](int i, int j) {
    return i*c + j;
  };
  rep(i, r) rep(j, c-1) {
    int a;
    cin >> a;
    G[num(i, j)].emplace_back(num(i, j+1), a);
    G[num(i, j+1)].emplace_back(num(i, j), a);
  }
  rep(i, r-1) rep(j, c) {
    int b;
    cin >> b;
    G[num(i, j)].emplace_back(num(i+1, j), b);
    G[num(i+1, j)].emplace_back(num(i+1, j)+r*c, 1);
    G[num(i, j)+r*c].emplace_back(num(i, j), 0);
    G[num(i+1, j)+r*c].emplace_back(num(i, j)+r*c, 1);
  }
  PQG<P> q;
  q.emplace(0, 0);
  vi dist(r*c*2, INF);
  dist[0] = 0;
  while(not q.empty()) {
    auto [d, now] = q.top();
    q.pop();
    if(d != dist[now]) continue;
    for(auto [ne, c]:G[now]) {
      if(chmin(dist[ne], d+c)) {
        q.emplace(d+c, ne);
      }
    }
  }
  cout << dist[r*c-1] << endl;
}