#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
int cnt = count_if(d.begin(), d.end(), [&](int x){
return x > 0;
});
vector adj(n + cnt, multiset<pair<int, int>>());
for(int i = 0; i + 1 < n; i++)
{
adj[i].insert({i + 1, l[i]});
adj[i + 1].insert({i, l[i]});
}
for(int i = 0, j = 0; i < n; i++)
{
if(d[i] == 0)
continue;
adj[i].insert({n + j, d[i]});
adj[n + j].insert({i, d[i]});
j++;
}
long long mn = 1e18 + 10;
vector<long long> dis(n + cnt);
auto bfs = [&](int start) -> void
{
pqg<pair<int, long long>> pq;
dis.assign(n + cnt, 1e18 + 10);
pq.push({start, 0});
while(not pq.empty())
{
auto [u, c] = pq.top();
pq.pop();
if(dis[u] <= c)
continue;
dis[u] = c;
for(auto [v, w]: adj[u])
pq.push({v, c + w});
}
};
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
adj[i].insert({j, C});
adj[j].insert({i, C});
int mx = 0;
for(int k = 0; k < n + cnt; k++)
{
bfs(k);
int s = *max_element(dis.begin(), dis.end());
if(mx < s)
mx = s;
}
if(mn > mx)
mn = mx;
adj[i].erase(adj[i].find({j, C}));
adj[j].erase(adj[j].find({i, C}));
}
}
return mn;
}
