WeekOfCode36_Problem_4

// code_report Solution
// https://youtu.be/dehTDLmuDKk

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

using ll = long long;
ll const MX = static_cast <ll> (1e5 + 1);
ll heights[MX], prices[MX], dp[MX];

int main ()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> heights[i];
	for (int i = 2; i <= n; i++) cin >> prices [i];

	stack<pair<ll,ll>> s;

	// iterating backwards
	for (int i = n; i >= 1; i--)
	{
		dp[i]   = static_cast <ll> (1e16); // minimum sum if Mason was actually student i
		ll temp = static_cast <ll> (1e16);

		while (!s.empty () && heights[s.top ().first] <= heights[i]) // process students IF height of student in stack is <= current student height
		{
			ll next_temp = s.top ().second;
			dp[i] = min (dp[i], next_temp - i + heights[i]); // THESE TWO LINES WORK TOGETHER
			temp  = min (temp,  next_temp);
			s.pop ();
		}

		if (s.empty ()) {
			dp[i] = min (dp[i], n + 1ll - i);
		} 
		else {
			auto j = s.top ().first; // index of element to the right, will always be have height > current height
			dp[i] = min (dp[i], j - i + dp[j] + heights[j] - heights[i] + prices[j]); // THIS LINE WORKS BY ITSELF
		}

		temp = min (temp, dp[i] + i - heights[i] + prices[i]); // THESE TWO LINES WORK TOGETHER
		s.push (make_pair (i * 1ll, temp));
	}

	cout << dp[1] << endl;

	return 0;
}