#include<iostream>

#include<algorithm>

using namespace std;

#define maxn 10010

int n,m,k,ans;

int need[maxn],tim[maxn],from[maxn],to[maxn],sum[maxn],last[maxn],mintime[maxn],e[maxn];

void fast(int x)

{

    while(x--)//枚举加速器

    {

        e[n]=e[n-]=n;//每次都初始化影响点

        int now,Max=-;//now为影响最大的点

        for(int i=n-;i>=;i--)//从后面推回去

        {

            if(mintime[i+]<=last[i+]) e[i]=i+;//如果要等待 最多影响到下一个

            else e[i]=e[i+];//如果不用等待 就会影响到后面的

        }

        for(int i=;i<n;i++)//枚举边

        {

            int temp=sum[e[i]]-sum[i];//枚举影响

            if(temp>Max&&need[i]>)//找出最大影响和位置 并且时间要大于1

            {

                Max=temp;

                now=i;

            }

        }

        ans-=Max;//答案减去影响到的人数

        need[now]--;//加速的时间减去

        for(int i=;i<=n;i++) mintime[i]=max(mintime[i-],last[i-])+need[i-];//重新计算每个点的最短时间

    }

}

int main()

{

    cin>>n>>m>>k;

    for(int i=;i<n;i++) cin>>need[i];

    for(int i=;i<=m;i++)

    {

        cin>>tim[i]>>from[i]>>to[i];

        last[from[i]]=max(last[from[i]],tim[i]);//此点的最迟时间为每个人从此点出发的最小值

        sum[to[i]]++;//在to[i]下车的人数+1

    }

    mintime[]=last[];//第一个点初始化

    for(int i=;i<=n;i++) sum[i]+=sum[i-]; //前缀和

    for(int i=;i<=n;i++) mintime[i]=max(mintime[i-],last[i-])+need[i-];//计算到达每个点所需要的最短时间

                                                                           //最后一个人到前一个站点的时间和到这个点的时间取max

    for(int i=;i<=m;i++) ans+=mintime[to[i]]-tim[i];//计算没有用加速器的答案 后面再减去用加速器的时间

    fast(k);//加速辣

    cout<<ans;

}