stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <cstdlib>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

//#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF (1<<31)-1;

#define mem(a) (memset(a,0,sizeof(a)))

struct P{

    int x,y;

}H[200000];

vector<int>G[200000];

int POS(int k,int value){

    int mid;

    int left = 0;

    int len = G[k].size();

    int right = len - 1;

    //cout<<" "<<k<<"A"<<value<<endl;

    while(left <= right){

 

        // 确保中点靠近区间的起点

        mid = left + (right-left)/2;

        //cout<<mid<<endl;

        //cout<<"mid= "<<mid<<" "<<left<<" "<<right<<endl;

        // 如果找到则返回

        if(G[k][mid] == value) return mid;

        // 将中点赋给终点

        else if(G[k][mid] > value) right = mid;

        // 将中点加一赋给起点

        else left = mid + 1;

    }

    return -1;

}

set<int>::iterator it;

int main()

{

    set<int>s;

    int N,M;

    int x,y;

    cin>>N>>M;

    for(int i=1;i<=M;i++){

        cin>>x>>y;

        H[i].x = x;

        H[i].y = y;

        G[x].push_back(y);

        s.insert(x);

    }

    for(int i=1;i<=N;i++){

        sort(G[i].begin(),G[i].end());

    }

 

 

    for(int i=1;i<=M;i++){

        cout<<setw(6)<<setfill('0')<<H[i].x;

        cout<<setw(6)<<setfill('0')<<POS(H[i].x,H[i].y)+1<<endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

typedef struct Node {

    int id, p, y, s;

} Node;

Node node[maxn] = { 0 };

bool cmp(Node &a, Node &b) {

    if (a.p == b.p) return a.y < b.y;

    return a.p < b.p;

}

bool cov(Node &a, Node &b) {

    return a.id < b.id;

}



int main() {

    int n, m;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d%d", &node[i].p, &node[i].y);

        node[i].id = i;

    }

    sort(node + 1, node + n + 1, cmp);

    int cnt = 1;

    for (int i = 1; i <= n; i++)

        if (node[i].p == node[i - 1].p) node[i].s = ++cnt;

        else node[i].s = cnt = 1;

    sort(node + 1, node + n + 1, cov);

    for (int i = 1; i <= n; i++)

        printf("%06d%06d\n", node[i].p, node[i].s);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>



typedef struct {

    int idx;

    int per;

    int year;

    char id[16];

} City;



int compCity(const void* aa, const void* bb) {

    City* a = (City*)aa;

    City* b = (City*)bb;



    if (a->per < b->per) return -1;

    else if (a->per > b->per) return 1;

    else if (a->year < b->year) return -1;

    return 1;

}



int compIdx(const void* aa, const void* bb) {

    City* a = (City*)aa;

    City* b = (City*)bb;



    if (a->idx < b->idx) return -1;

    return 1;

}



int main() {

    int N = 0, M = 0;

    scanf("%d %d", &N, &M);

    City *city = new City[M]();

    for (int i = 0; i < M; i++) {

        city[i].idx = i;

        scanf("%d %d", &(city[i].per), &(city[i].year));

    }



    qsort(city, M, sizeof(City), compCity);



    for (int i = 0, j = 1, p = city[0].per; i < M; i++) {

        if (p != city[i].per) {

            j = 1;

            p = city[i].per;

        }

        sprintf(city[i].id, "%06d%06d", p, j++);

    }



    qsort(city, M, sizeof(City), compIdx);



    for (int i = 0; i < M; i++) {

        printf("%s\n", city[i].id);

    }



    delete[] city;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

typedef struct Node {

    int id, p, y, s;

} Node;

Node node[maxn] = { 0 };

bool cmp(Node &a, Node &b) {

    if (a.p == b.p) return a.y < b.y;

    return a.p < b.p;

}

bool cov(Node &a, Node &b) {

    return a.id < b.id;

}



int main() {

    int n, m;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d%d", &node[i].p, &node[i].y);

        node[i].id = i;

    }

    sort(node + 1, node + n + 1, cmp);

    int cnt = 1;

    for (int i = 1; i <= n; i++)

        if (node[i].p == node[i - 1].p) node[i].s = ++cnt;

        else node[i].s = cnt = 1;

    sort(node + 1, node + n + 1, cov);

    for (int i = 1; i <= n; i++)

        printf("%06d%06d\n", node[i].p, node[i].s);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<algorithm>



using namespace std;



struct temp

{

    int rank;

    int p;

    int y;

}a[100005];



int cmp(temp x, temp y)

{

    if(x.p != y.p)

        return x.p<y.p;

    else

        return x.y<y.y;

}



int main()

{

    int n,m;

    while(cin >> n >> m)

    {

        int b[100005];

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

    {

        a[i].rank = i;

        cin >> a[i].p >> a[i].y;

        b[i] = a[i].p;

    }



    sort(a,a+m,cmp);

    int f = a[0].p,flag = 1;

    int x[100005];



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

    {

        if(a[i].p != f)

        {

            flag = 1;

            f = a[i].p;

        }

        x[a[i].rank] = flag++;

    }



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

        printf("%06d%06d\n",b[i],x[i]);



    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

typedef struct Node {

    int id, p, y, s;

} Node;

Node node[maxn] = { 0 };

bool cmp(Node &a, Node &b) {

    if (a.p == b.p) return a.y < b.y;

    return a.p < b.p;

}

bool cov(Node &a, Node &b) {

    return a.id < b.id;

}



int main() {

    int n, m;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d%d", &node[i].p, &node[i].y);

        node[i].id = i;

    }

    sort(node + 1, node + n + 1, cmp);

    int cnt = 1;

    for (int i = 1; i <= n; i++)

        if (node[i].p == node[i - 1].p) node[i].s = ++cnt;

        else node[i].s = cnt = 1;

    sort(node + 1, node + n + 1, cov);

    for (int i = 1; i <= n; i++)

        printf("%06d%06d\n", node[i].p, node[i].s);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



const int N = 1e5+5;



struct node{

    int aa,bb;

};



int main()

{

    int n,m,i,j,k;

    cin>>n>>m;

    int p[m+2],y[m+2];

    //priority_queue < pair<int,int> > pq;

    //map < node ,int> mp;

    map < pair<int,int> ,int> mp;

    map < int, vector<int> > v;

    set <int> st;

    //node pp;

    pair <int,int> pp;



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

    {

        cin>>p[i]>>y[i];

        v[p[i]].push_back(y[i]);

        st.insert(p[i]);

    }



    for(auto ii: st)

    {

        sort(v[ii].begin(),v[ii].end());

        for(i=0; i<v[ii].size(); i++)

        {

            //pp.aa=ii;

            //pp.bb=v[ii][i];

            pp= make_pair(ii,v[ii][i]);

            mp[pp]=i+1;

        }

    }





    string s;



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

    {

        s="000000000000";



        k=p[i];

        j=5;

        while(k)

        {

            s[j--]=(char) (k%10)+'0';

            k/=10;

        }

        ///////////////

        pp= make_pair(p[i],y[i]);

        //pp.aa=p[i];

        //pp.bb=y[i];

        k=mp[pp];

        j=11;

        while(k)

        {

            s[j--]=(char) (k%10)+'0';

            k/=10;

        }



        cout<<s<<endl;

    }





    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

typedef struct Node {

    int id, p, y, s;

} Node;

Node node[maxn] = { 0 };

bool cmp(Node &a, Node &b) {

    if (a.p == b.p) return a.y < b.y;

    return a.p < b.p;

}

bool cov(Node &a, Node &b) {

    return a.id < b.id;

}



int main() {

    int n, m;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d%d", &node[i].p, &node[i].y);

        node[i].id = i;

    }

    sort(node + 1, node + n + 1, cmp);

    int cnt = 1;

    for (int i = 1; i <= n; i++)

        if (node[i].p == node[i - 1].p) node[i].s = ++cnt;

        else node[i].s = cnt = 1;

    sort(node + 1, node + n + 1, cov);

    for (int i = 1; i <= n; i++)

        printf("%06d%06d\n", node[i].p, node[i].s);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

    ll n,m;

    cin>>n>>m;

    vector<pair<ll,ll> >pr(m);

    map<ll,pair<ll,ll> >mp;

    vector<ll>v(m);

    for(ll i=0;i<m;++i)

    {

        cin>>pr[i].first>>pr[i].second;

        v[i] = pr[i].second;

    }

    sort(pr.begin(),pr.end());

    ll c=1;



    for(ll i=0;i<m;++i)

    {

        mp.insert({pr[i].second,{pr[i].first,c}});

        ++c;

    if(pr[i].first!=pr[i+1].first)

            c = 1;

    }



    for(ll i=0;i<m;++i)

    {

        printf("%.6lld%.6lld\n",mp[v[i]].first,mp[v[i]].second);

    }

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

typedef struct Node {

    int id, p, y, s;

} Node;

Node node[maxn] = { 0 };

bool cmp(Node &a, Node &b) {

    if (a.p == b.p) return a.y < b.y;

    return a.p < b.p;

}

bool cov(Node &a, Node &b) {

    return a.id < b.id;

}



int main() {

    int n, m;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d%d", &node[i].p, &node[i].y);

        node[i].id = i;

    }

    sort(node + 1, node + n + 1, cmp);

    int cnt = 1;

    for (int i = 1; i <= n; i++)

        if (node[i].p == node[i - 1].p) node[i].s = ++cnt;

        else node[i].s = cnt = 1;

    sort(node + 1, node + n + 1, cov);

    for (int i = 1; i <= n; i++)

        printf("%06d%06d\n", node[i].p, node[i].s);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<vector>

using namespace std;

typedef  long long ll;

int N,M,P,Y;

const int maxm=(int)1e5+5;

struct city{

int p;

int y;

int i;

int flag;

city(){

    flag = 0;

}

};

city C[maxm];

int tot;

bool cmp1(city city1,city city2){

    return city1.p<city2.p ||(city1.p==city2.p&&city1.y<city2.y);

}

bool cmp2(city city1,city city2){

    return city1.i<city2.i;

}

int main(){

    scanf("%d%d",&N,&M);

    tot=0;

    memset(C,0,sizeof(C));

    for(int i=0;i<M;i++){

        struct city tmp;

        scanf("%d%d",&P,&Y);

        tmp.p=P;tmp.y=Y;tmp.i=i;

        C[tot]=tmp;

        tot++;

    }

    sort(C,C + M,cmp1);

    C[0].flag=1;

    for(int i=1;i<M;i++){

        if(C[i].p==C[i-1].p)C[i].flag=C[i-1].flag+1;

        else C[i].flag=1;

    }

     sort(C,C + M,cmp2);

     for(int i=0;i<M;i++){

        printf("%06d%06d\n",C[i].p,C[i].flag);

     }

    //for(int i=0;i<M;i++)

      //  cout<<"p:"<<C[i].p<<"y:"<<C[i].y<<"flag:"<<C[i].flag<<"i:"<<C[i].i<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

struct ss{

    int rank;

    int p;

    int y;

}a[100005];

int cmp(ss x,ss y){

    if(x.p!=y.p) return x.p<y.p;

    else return x.y<y.y;

}

int main()

{

    int n ,m;

    scanf("%d%d",&n,&m);

    int b[100005];

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

        a[i].rank=i;

        scanf("%d%d",&a[i].p,&a[i].y);

        b[i]=a[i].p;

    }

    sort(a,a+m,cmp);

    int f=a[0].p,flag=1;

    int x[100005];

    

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

        if(a[i].p!=f) {flag=1;f=a[i].p;}

        x[a[i].rank]=flag++;

    }



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

        printf("%06d%06d\n",b[i],x[i]);

    return 0;



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <string>

using namespace std;



struct CITY{

    //int id;

    int p;

    int year;

    int no;

};

CITY citys[100000];

string ids[100000];



int cmp(CITY a, CITY b)

{

    if(a.p!=b.p)

    {

        return a.p<b.p;

    }

    else

    {

        return a.year<b.year;

    }

}



string id2String(int data)

{

    string s="";

    int i,d;

    for(i=0;i<6;i++)

    {

        d = data%10;

        data = data/10;

        s = to_string(d)+s;

    }

    return s;

}





int main()

{

 int N,M;

 int i,j,number=1,p_pre=0,data2;

 char s[6],d[6],id[12];



 cin>>N>>M;

 for(i=0;i<M;i++)

 {

     citys[i].no = i;

     cin>>citys[i].p>>citys[i].year;

 }

 sort(citys, citys+M,cmp);



 for(i=0;i<M;i++)

 {

     if(p_pre == citys[i].p)

     {

        number++;

     }

     else

     {

         number=1;

         p_pre = citys[i].p;

     }

     ids[citys[i].no] = id2String(citys[i].p)+id2String(number);

 }



 for(i=0;i<M;i++)

 {

    cout<<ids[i]<<endl;

 }

 return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



struct T{

	int y, p, i, j;

}a[100005];



bool cmp(T a, T b){

	if(a.y == b.y)

		return a.p < b.p;

	return a.y < b.y;

}



bool cmp1(T a, T b){

	return a.i < b.i;

}



int main(){

	int n, m;

	cin >> n >> m;

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

		scanf("%d %d",&a[i].y,&a[i].p);

		a[i].i = i;

	}

	sort(a+1,a+1+m,cmp);

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

//		printf("%d %d\n",a[i].y,a[i].p);	

	int x = 1, y = 1;

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

		if(a[i].y > x){

			x = a[i].y;

			y = 1;	

		}

		a[i].j = y++;

//		printf("%06d%06d\n",x,y++);

	}

	sort(a+1,a+1+m,cmp1);

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

		printf("%06d%06d\n",a[i].y,a[i].j);

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

	ll n,m;

	cin>>n>>m;

	ll p[m],y[m];

	vector<ll>py[100001];

	for(int i=0;i<m;i++)cin>>p[i]>>y[i];





	for(int i=0;i<m;i++)py[p[i]].push_back(y[i]);

	for(int i=0;i<n;i++)sort(py[i+1].begin(),py[i+1].end());

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

		printf ("%012lld\n",ll(p[i])*1000000+ int(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin())+1);

	}



/*	for(int i=0;i<m;i++){

		printf("%lld\n",*lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]));

	}*/

	//	for(int i=0;i<m;i++)num[y[i]]=i;

	//sort(y,y+m);

	 /*for( vector<ll>::iterator i=begin(py);i!=end(py);++i) {

	      std::cout << i << std::endl;

	   }*/

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

	ll n,m;

	cin>>n>>m;

	ll p[m],y[m];

	vector<ll>py[n+1];

	for(int i=0;i<m;i++)cin>>p[i]>>y[i];





	for(int i=0;i<m;i++)py[p[i]].push_back(y[i]);

	for(int i=0;i<n;i++)sort(py[i+1].begin(),py[i+1].end());

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

		printf ("%012lld\n",ll(p[i])*1000000+ int(lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i])-py[p[i]].begin())+1);

	}



/*	for(int i=0;i<m;i++){

		printf("%lld\n",*lower_bound(py[p[i]].begin(),py[p[i]].end(),y[i]));

	}*/

	//	for(int i=0;i<m;i++)num[y[i]]=i;

	//sort(y,y+m);

	 /*for( vector<ll>::iterator i=begin(py);i!=end(py);++i) {

	      std::cout << i << std::endl;

	   }*/

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <random>

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

int main()

{

	vector<P> v[100001];

	int n, m;

	cin>>n>>m;

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

		int p, y;

		cin>>p>>y;

		v[p].push_back(P(y, i));

	}

	string s[100001];

	ll ans[100001];

	for(ll i=1; i<=n; i++){

		sort(v[i].begin(), v[i].end());

		for(ll j=0; j<v[i].size(); j++){

			int t=v[i][j].second;

			ans[t]=i*1000000+j+1;

			ll ans1=ans[t];

			int ct=0;

			while(ans1>0){

				ans1/=10;

				ct++;

			}

			for(int k=0; k<12-ct; k++) s[t]+='0';

		}

	}

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

		cout<<s[i]<<ans[i]<<endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <random>

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

int main()

{

	vector<P> v[100001];

	int n, m;

	cin>>n>>m;

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

		int p, y;

		cin>>p>>y;

		v[p].push_back(P(y, i));

	}

	ll ans[100001];

	for(ll i=1; i<=n; i++){

		sort(v[i].begin(), v[i].end());

		for(ll j=0; j<v[i].size(); j++){

			int t=v[i][j].second;

			ans[t]=i*1000000+j+1;

		}

	}

	for(int i=0; i<m; i++) printf("%012lld\n", ans[i]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<cmath>

using namespace std;



int main() {

  int N, T;

  vector<int> t;



  cin >> N >> T;

  t.resize(N);



  for (int i = 0; i < N; i++)

    cin >> t[i];



  int64_t ans = 0;

  for (int i = 1; i < N; i++) {

    if (t[i] - t[i-1] >= T)

      ans += T;

    else

      ans += t[i] - t[i-1];

  }

  ans += T;



  cout << ans << endl;

}


// Optimized solution to the same problem (faster):
#include<cstdio>



int main() {

  int N, T; scanf("%d %d\n", &N, &T);

  int t[N];



  for (int i = 0; i < N; i++)

    scanf("%d", &t[i]);



  long ans = 0;

  for (int i = 1; i < N; i++) {

    if (t[i] - t[i-1] >= T)

      ans += T;

    else

      ans += t[i] - t[i-1];

  }

  ans += T;



  printf("%ld\n", ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <assert.h>



using namespace std;



#define N 100005



int dsu[N],ret[N];

long long W[N];

vector<int> edgeS[N];

bool isGoodEdge[N];



int f(int x) {

  if(x==dsu[x]) {

    return x;

  }

  return dsu[x] = f(dsu[x]);

}

void merge(int x,int y,int id,int wei) {

  x = f(x),y = f(y);

  if(x!=y) {

    if(edgeS[x].size()<edgeS[y].size()) {

      swap(x,y);

    }

    dsu[y] = x;

    W[x] += W[y];

    while(edgeS[y].size()>0) {

      edgeS[x].push_back(edgeS[y].back());

      edgeS[y].pop_back();

    }

  }

  edgeS[x].push_back(id);

  if(W[x]>=wei) {

    while(edgeS[x].size()>0) {

      isGoodEdge[edgeS[x].back()] = true;

      edgeS[x].pop_back();

    }

  }

}

void solve() {

  int n,m;

  scanf("%d %d",&n,&m);

  pair<int,pair<int,int> > edgeS[N];

  for(int i=1;i<=n;++i) {

    dsu[i] = i;

    scanf("%lld",&W[i]);

  }

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

    scanf("%d %d %d",&edgeS[i].second.first,&edgeS[i].second.second,&edgeS[i].first);

  }

  sort(edgeS,edgeS+m);

  int R = 0;

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

    int w = edgeS[i].first;

    int a = edgeS[i].second.first, b = edgeS[i].second.second;

    merge(a,b,i,w);

  }

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

    if(isGoodEdge[i]) {

      ++R;

    }

  }

  printf("%d\n",m - R);

}



int main() {

  //freopen("input.txt","r",stdin);

  solve();

  return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <assert.h>

#include <memory.h>



using namespace std;



#define N 100001



int dsu[N],numUnsat[N];

long long sum[N];

int f(int x) {

  return dsu[x] ==x ? x : dsu[x] = f(dsu[x]);

}

void merge(int &ret,int x,int y,int wei) {

  x = f(x),y = f(y);

  if(x==y) {

    ++numUnsat[x];

  } else {

    sum[x] += sum[y];

    dsu[y] = x;

    numUnsat[x] = numUnsat[x] + numUnsat[y] + 1;

  }

  if(sum[x]>=wei) {

    ret += numUnsat[x];

    numUnsat[x] = 0;

  }

}

void solve() {

  int n,m;scanf("%d %d",&n,&m);

  pair<int,pair<int,int> > edge[N];

  for(int i=1;i<=n;++i) {

    int x;scanf("%d",&x);

    dsu[i] = i;

    numUnsat[i] = 0;

    sum[i] = x;

  }

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

    int a,b,w;scanf("%d %d %d ",&a,&b,&w);

    edge[i] = make_pair(w,make_pair(a,b));

  }

  sort(edge,edge+m);

  int ret = 0;

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

    merge(ret, edge[i].second.first,edge[i].second.second,edge[i].first);

  }

  printf("%d\n",m-ret);

}



int main() {

  //freopen("input.txt","r",stdin);

  solve();

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)

#pragma GCC optimize(2)

#include<iostream>

#include<algorithm>

#define l first

#define r second

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int N=200010;

const ll mod=998244353;

int n,k;

ll f[N],s[N];

pii a[N];

int main()

{

    IO;

    int T=1;

    //cin>>T;

    while(T--)

    {

        cin>>n>>k;

        for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;

        f[1]=1;

        s[1]=1;

        for(int i=2;i<=n;i++)

        {

            for(int j=1;j<=k;j++)

                f[i]=(f[i]+s[max(0,i-a[j].l)]-s[max(0,i-a[j].r-1)])%mod;;

            s[i]=(s[i-1]+f[i])%mod;

        }    

        cout<<(f[n]+mod)%mod<<'\n';

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#define mod 998244353

#define max(a,b) ((a)>(b)?(a):(b))

struct interval{

    int l,r;

}a[200003];

long long f[200003]={0,1},s[200003]={0,1};

int n,k;

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=k;i++) scanf("%d%d",&a[i].l,&a[i].r);

    for(int i=2;i<=n;i++){

        for(int j=1;j<=k;j++){

            if(i>a[j].l) f[i]=(f[i]+(s[i-a[j].l]-s[max(i-a[j].r-1,0)])%mod)%mod;

        }

        s[i]=(s[i-1]+f[i])%mod;

    }

    printf("%lld\n",(f[n]+mod)%mod);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int dp[1010][1010];

int main()

{

	int n,m,q,i,x,y,j,k;

	scanf("%d%d%d",&n,&m,&q);

	memset(dp,0,sizeof(dp));

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

	{

		scanf("%d%d",&x,&y);

		dp[x][y]++;

	}

	for(j=1; j<n; j++)

		for(i=1; i+j<=n; i++)

		{

			k=i+j;

			dp[i][k]=dp[i][k]+dp[i+1][k]+dp[i][k-1];

			if(j>1)dp[i][k]-=dp[i+1][k-1];

		}

	while(q--)

	{

		scanf("%d%d",&x,&y);

		printf("%d\n",dp[x][y]);

	}







	return 0;

}

// Optimized solution to the same problem (faster):
//看题解了，重做 

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int NN = 700;

int x, y, ans, n, m, q, a[NN][NN], b[NN][NN], c[NN][NN];



int main(){

	//freopen("atcoderabc106d.in", "r", stdin);

	

	scanf("%d%d%d", &n, &m, &q);

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

		scanf("%d%d", &x, &y);

		a[x][y]++;

	}

	

	for (int i=1; i<=n; i++)

		for (int j=i; j<=n; j++)

			for (int k=i; k<=j; k++) b[i][j] += a[i][k];  //b[i][j]表示以i为起点，终点在j及j之前的边的个数 

	

	for (int i=1; i<=n; i++)

		for (int j=i; j<=n; j++)

			for (int k=i; k<=j; k++) c[i][j] += b[k][j];  //c[i][j]即为所求 

	

	

	while (q--){

		scanf("%d%d", &x, &y);

		printf("%d\n", c[x][y]);

		//printf("%d %d %d\n", r[y] - l[x-1], r[y], l[x-1]);

	} 

	

	return 0;

} 

// Fastest known solution for this problem: