Network

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define mp make_pair
#define faster_io() ios_base::sync_with_stdio(false)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define vii vector<pair<int,int>>

const int INF = 1000000000;
const ll INFLL = 100000000000000000ll;
const ll MOD = 1000000007;

// ----------------------------------------------------------------------------------------------------------

int aa[1005], bb[1005], cc[1005], buf[6][64500], pos[6], sz[6], n, m;

int tryOut(vector<int> p)
{
    int buf_sz = 0, curr = 0, ret = 0;
    f(i,1,n) pos[i] = 1;

    f(i,1,m)
    {
        int a = aa[i], b = bb[i], c = cc[i];
        buf_sz += c-b+1;
        buf[a][b] = c;
        int curr_msg = p[curr];

        while(buf[curr_msg][pos[curr_msg]])
        {
            int nx = buf[curr_msg][pos[curr_msg]] + 1;
            buf_sz -= nx - pos[curr_msg];
            buf[curr_msg][pos[curr_msg]] = 0;
            pos[curr_msg] = nx;
            if(pos[curr_msg] > sz[curr_msg])
            {
                curr++;
                if(curr < SZ(p)) curr_msg = p[curr];
            }
        }

        ret = max(ret, buf_sz);
    }

    return ret;
}

int main()
{
    f(t,1,1000000)
    {
        cin >> n >> m;
        if(n <= 0) return 0;

        f(i,1,n) cin >> sz[i];
        f(i,1,m) cin >> aa[i] >> bb[i] >> cc[i];

        vector<int> perm;
        f(i,1,n) perm.pb(i);

        int ans = 999999;

        do
        {
            int k = tryOut(perm);
            ans = min(ans, k);
        }while(next_permutation(all(perm)));

        cout << "Case " << t << ": " << ans << "\n\n";
    }
}