#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];
  }
};