#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500;
vector<pair<int, int> > graph[1+2*MAX_N];
long long dist[1+2*MAX_N];
void dijkstra(int nod, int n) {
for(int i = 0; i < 2 * n; ++i)
dist[i] = 1LL<<60;
deque<int> q;
dist[nod] = 0;
q.push_back(nod);
while(!q.empty()) {
int nod = q.front();
q.pop_front();
for(auto it: graph[nod])
if(dist[nod] + it.second < dist[it.first]) {
dist[it.first] = dist[nod] + it.second;
q.push_back(it.first);
}
}
}
long long getDiam(int n) {
long long rez = 0LL;
for(int i = 0; i < 2 * n; ++i)
if(!graph[i].empty()) {
dijkstra(i, n);
for(int j = 0; j < 2 * n; ++j)
if(!graph[j].empty())
rez = max(rez, dist[j]);
}
return rez;
}
long long f(int n, int x, int c) {
long long rez = 1LL<<60;
for(int i = 0; i + x < n; ++i) {
graph[i].push_back(make_pair(i + x, c));
graph[i + x].push_back(make_pair(i, c));
rez = min(rez, getDiam(n));
graph[i].pop_back();
graph[i + x].pop_back();
}
return rez;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
for(int i = 0; i < n - 1; ++i) {
graph[i].push_back(make_pair(i + 1, l[i]));
graph[i + 1].push_back(make_pair(i, l[i]));
}
for(int i = 0; i < n; ++i)
if(d[i] != 0) {
graph[i].push_back(make_pair(i + n, d[i]));
graph[i + n].push_back(make_pair(i, d[i]));
}
long long xd = 1LL<<60;
for(int i = 1; i < n; ++i)
xd = min(xd, f(n, i, c));
return xd;
}
