#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;
 
struct SteelMill {
  long long cheapest(int goal, vector <int> shipmentCost, vector <int> shipmentSize, vector <int> costPerKg)
  {
    vector<long long> f(goal + 1, oo);
    f[0] = 0;
    for (int i = 0; i < shipmentCost.size(); i++)
    {
      vector<long long> newF = f;
      deque<pair<long long, int>> dq;
      dq.push_back({0, 0});
      for (int j = 1; j <= goal; j++)
      {
        while (j - dq.front().second > shipmentSize[i])
          dq.pop_front();
        newF[j] = min(newF[j], dq.front().first + 1LL * costPerKg[i] * j + shipmentCost[i]);
        long long value = f[j] - 1LL * costPerKg[i] * j;
        while (!dq.empty() && value <= dq.back().first)
          dq.pop_back();
        dq.push_back({value, j});
      }
      f = newF;
    }
    return f[goal];
  }
};
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGxvbmcgbG9uZyBvbyA9IDFMTCA8PCA2MDsKCnN0cnVjdCBTdGVlbE1pbGwgewogIGxvbmcgbG9uZyBjaGVhcGVzdChpbnQgZ29hbCwgdmVjdG9yIDxpbnQ+IHNoaXBtZW50Q29zdCwgdmVjdG9yIDxpbnQ+IHNoaXBtZW50U2l6ZSwgdmVjdG9yIDxpbnQ+IGNvc3RQZXJLZykKICB7CiAgICB2ZWN0b3I8bG9uZyBsb25nPiBmKGdvYWwgKyAxLCBvbyk7CiAgICBmWzBdID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2hpcG1lbnRDb3N0LnNpemUoKTsgaSsrKQogICAgewogICAgICB2ZWN0b3I8bG9uZyBsb25nPiBuZXdGID0gZjsKICAgICAgZGVxdWU8cGFpcjxsb25nIGxvbmcsIGludD4+IGRxOwogICAgICBkcS5wdXNoX2JhY2soezAsIDB9KTsKICAgICAgZm9yIChpbnQgaiA9IDE7IGogPD0gZ29hbDsgaisrKQogICAgICB7CiAgICAgICAgd2hpbGUgKGogLSBkcS5mcm9udCgpLnNlY29uZCA+IHNoaXBtZW50U2l6ZVtpXSkKICAgICAgICAgIGRxLnBvcF9mcm9udCgpOwogICAgICAgIG5ld0Zbal0gPSBtaW4obmV3RltqXSwgZHEuZnJvbnQoKS5maXJzdCArIDFMTCAqIGNvc3RQZXJLZ1tpXSAqIGogKyBzaGlwbWVudENvc3RbaV0pOwogICAgICAgIGxvbmcgbG9uZyB2YWx1ZSA9IGZbal0gLSAxTEwgKiBjb3N0UGVyS2dbaV0gKiBqOwogICAgICAgIHdoaWxlICghZHEuZW1wdHkoKSAmJiB2YWx1ZSA8PSBkcS5iYWNrKCkuZmlyc3QpCiAgICAgICAgICBkcS5wb3BfYmFjaygpOwogICAgICAgIGRxLnB1c2hfYmFjayh7dmFsdWUsIGp9KTsKICAgICAgfQogICAgICBmID0gbmV3RjsKICAgIH0KICAgIHJldHVybiBmW2dvYWxdOwogIH0KfTsK