#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<iostream>
#define pb push_back
#define fi first
#define se second
#define sz(x)  x.size()
#define cl(x)  x.clear()
#define all(x)  x.begin() , x.end()
#define r(x)  scanf("%d", &x)
#define rr(x , y)  scanf("%d%d" , &x , &y)
#define rst(s)  scanf("%s" , s)
#define rl(x)  scanf("%lld" , &x)
#define rrl(x , y)  scanf("%lld%lld" , &x , &y)
#define w(x)  printf("%d" , x)
#define ww(x , y)  printf("%d %d" , x , y)
#define wl(x)  printf("%lld" , x)
#define wwl(x , y)  printf("%lld %lld" , x , y)
#define sp()  printf(" ")
#define en()  puts("")
#define rep(i , x , n)  for(int i = x ; i <= n ; i ++) 
#define per(i , n , x)  for(int i = n ; i >= x ; i --) 
#define mem0(x)  memset(x , 0 , sizeof(x))
#define mem_1(x)  memset(x , -1 , sizeof(x))
#define mem_inf(x)  memset(x , inf , sizeof(x))
#define mem__inf(x)  memset(x , -inf , sizeof(x))
#define p_queue priority_queue
#define debug(x)  cout << x << '\n'
#define ddebug(x , y)  cout << x << ' ' << y << '\n'
using namespace std ;
//mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef pair<int , ll> pil ;
typedef pair<ll , int> pli ;
const int inf = 0x3f3f3f3f ;
const int maxn = 4005 ;
const int maxm = 30 ;
const ll mod = 1e9 + 7 ;
int n , a[maxn] ;
struct node 
{  
	int x ;
	ll dis ; 
	bool operator < (node s) const 
	{ 
		return dis > s.dis ; 
	} 
} ;
int num , head[maxn] ;
struct Edge
{
	int v , next ; 
	int cap , flow ;
	ll cost ;
} edge[10000000] ;
void init()
{
	num = 0 ;
	memset(head , -1 , sizeof(head)) ;
}
void add_edge(int u , int v , int cap , int flow , ll cost)
{
	edge[num].v = v ;
	edge[num].cap = cap ;
	edge[num].flow = flow ;
	edge[num].cost = cost ;
	edge[num].next = head[u] ;
	head[u] = num ++ ;	
} 
struct Mincost
{
	int n , m , s , t ;
	int pre[maxn] ;
	ll dis[maxn] , h[maxn] ;
	priority_queue<node> q ;
	void init()
	{
		memset(dis , 0 , sizeof(dis)) ;
		memset(h , 0 , sizeof(h)) ;
	}
	void auto_addedge(int u , int v , int cap , int cost) 
	{
		add_edge(u , v , cap , 0 , cost) ;
		add_edge(v , u , 0 , 0 , -cost) ;
	}
	bool dij(int s , int t) 
	{
		ll up = 1e18 ;
		for(int i = 1 ; i <= n ; i++)
		{
			h[i] = min(h[i] + dis[i] , up) ;
			dis[i] = 1e18 , pre[i] = -1 ;
		}
		dis[s] = 0 , q.push(node{s , 0}) ;
		while(!q.empty())
		{
			int u = q.top().x , dist = q.top().dis ; 
			q.pop() ;
			if(dist > dis[u])  continue ;
			for(int i = head[u] ; i != -1 ; i = edge[i].next) 
			{
				Edge &e = edge[i] ; //链式前向星不能写成结构体的原因
				int v = edge[i].v ;
				if(e.cap > e.flow && dis[v] > dis[u] + e.cost + h[u] - h[v]) 
				{
					dis[v] = dis[u] + e.cost + h[u] - h[v] ;
					pre[v] = i ;
					q.push(node{v , dis[v]}) ;
				}
			}
		}
		return dis[t] < 1e18 ;
	}
	pil mincost_maxflow(int s, int t) 
	{
		int flow = 0 ;
		ll cost = 0 ;
		while(dij(s , t)) 
		{
			int min1 = inf ;
			ll fee = dis[t] + h[t] - h[s] ;
			for(int i = pre[t] ; i != -1 ; i = pre[edge[i ^ 1].v])
			  min1 = min(min1 , edge[i].cap - edge[i].flow) ;
			for(int i = pre[t] ; i != -1 ; i = pre[edge[i ^ 1].v])
			  edge[i].flow += min1 , edge[i^1].flow -= min1 ;
			flow += min1 , cost += fee * min1 ;
		}
		return make_pair(flow , cost) ;
	}
} mincost ;
int main()
{
	r(n) ;
	rep(i , 1 , n)  r(a[i]) ;
	init() ;
	mincost.init() ;
	mincost.n = 2 * n + 2 ;
	mincost.s = 2 * n + 1 ;
	mincost.t = 2 * n + 2 ;
	rep(i , 1 , n)  mincost.auto_addedge(mincost.s , i , 1 , 0) ;
	rep(i , 1 , n)  rep(j , 1 , n)
	  mincost.auto_addedge(i , j + n , 1 , -ll(a[i]) * abs(i - j)) ;
	rep(i , 1 , n)  mincost.auto_addedge(i + n , mincost.t , 1 , 0) ;
	for (int i = 1; i <= mincost.m ; i++)
	{
		int u , v , cap , cost ;
		scanf("%d%d%d%d", &u , &v , &cap , &cost) ;
		mincost.auto_addedge(u , v , cap , cost) ;
	}   
	pil ans = mincost.mincost_maxflow(mincost.s , mincost.t) ;
	wl(-ans.second) ;
	return 0;
}