akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main() {
	int n, ans; bool check;
	while (cin >> n) {
		ans = 0;
		for (int i = 1; i <= n; i++) {
			if (i <= 3) {
				if (i != 1) { ans++; } continue;
			}
			else {
				if (i % 2 == 0 || i % 3 == 0) continue;
				if (i % 6 != 1 && i % 6 != 5) continue;
				check = true;
				for (int j = 5; j * j <= i; j += 6) {
					if (i % (j + 0) == 0) { check = false; }
					if (i % (j + 2) == 0) { check = false; }
					if (check == false) { break; }
				}
				if (check == true) ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3068
#include <iostream>
using namespace std;

int main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    
    double max = 0;
    int max_water = 0, max_sugar = 0;
    for(int a = 0; a <= F; a += 100*A) {
        for(int b = 0; a + b <= F; b += 100*B) {
            int water = a + b;
            int sugar_limit = min(F - water, E * (water / 100));
            for(int c = 0; c <= sugar_limit; c += C) {
                int d = (sugar_limit - c) / D * D;
                int sugar = c + d;
                double res = (double)sugar / (water + sugar);
                if(max <= res) {
                    max = res, max_water = water, max_sugar = sugar;
                }
            }
        }
    }
    
    cout << max_water + max_sugar << " " << max_sugar << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i< int (n); i++)
using namespace std;
typedef long long ll;

int main(){
ll a, b, n;
cin >> a >> b >>n;
ll x = min(n,b-1);
ll ans = a*x/b; 
cout << ans << endl;

}

Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <map>

int main(){

  //char S[100005];
  //scanf("%s",S);
  std::string S;
  std::cin>>S;
  //printf("%c\n",S[0]);
  int size = S.size();
  std::vector<int> ans(size);

  for (int j=0; j<2; j++){
    int cnt=0;
    for (int i=0; i<size; i++){
      if (S[i]=='L'){
        ans[i-1]+=int((cnt+1)/2);
        ans[i]+=int(cnt/2);
        cnt=0;
      } else {
        cnt++;
      }
    }
    std::reverse(ans.begin(), ans.end());
    std::reverse(S.begin(), S.end());
    for (int i=0; i<size; i++){
      if (S[i]=='L'){
        S[i]='R';
      } else {
        S[i] = 'L';
      }
    }
  }
  
  for (int i=0; i<size; i++){
    printf("%d%c",ans[i], i==size-1?'\n':' ');
  }
  return 0;
}

Measured memory_bytes: 1088
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
#define pb push_back
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/__gcd((a),(b))
#define clr(x) x.clear()
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vi>
#define mp make_pair
#define hell 1000000007

using namespace std;

bool compare(pair<string,pair<int,int>> &a,pair<string,pair<int,int>> &b)
{
    if(a.first!=b.first)
        return a.first<b.first;
    else
        return a.second.first>b.second.first;
}

int main()
{
    IOS
    int n;
    cin>>n;
    cin.ignore();
    vector<pair<string,pair<int,int>>> v;
    for(int i=1;i<=n;i++)
    {
    string str;
    int p;
    cin>>str>>p;
    cin.ignore();
    v.pb({str,{p,i}});
    }
    sort(v.begin(),v.end(),compare);
    for(int i=0;i<n;i++)
        cout<<v[i].second.second<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define Pi 3.1415926535
#define MOD = 1e9+7;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}

int solve(){
    string s; cin >> s;
    int w; cin >> w;
    for(int i = 0; i < s.size(); i += w){
        cout << s[i];
    }
    cout << endl;

    return 0;
}

int main(){
    cin.tie(0);
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
int main(void){
  uint64_t n,i,j=0,ct=0,tmp=0,abs;
  cin>>n;

  vector<pair<uint64_t,uint64_t> > data(n);
  for(i=0;i<n;i++){
    cin>>data.at(i).first;
    data.at(i).second=i+1;
  }
  for(i=0;i<n;i++){
    if(data.at(i).first!=data.at(i).second){
      j++;
      if(data.at(i).first>data.at(i).second){
        abs=data.at(i).first-data.at(i).second;
      }else{
        abs=data.at(i).second-data.at(i).first;
      }

      if(j==1){
      tmp=abs;
    }else if(j==2){
      if(tmp==abs){
        ct++;
      }
    }}
  }

  if(ct==0&&j==0){
    cout<<"YES"<<endl;
  }else if(ct==1&&j==2){
    cout<<"YES"<<endl;
  }else{
      cout<<"NO"<<endl;
  }

return 0;
}


Measured memory_bytes: 256
# abc174_b.py
# https://atcoder.jp/contests/abc174/tasks/abc174_b

global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, D = list(map(int, lines[0].split()))
    values = list(map(int, lines[0].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    valueses = list()
    for i in range(N):
        valueses.append(list(map(int, lines[i+1].split())))

    result = 0
    for values in valueses:
        x, y = values
        d = (x**2 + y**2)**0.5
        if d <= D:
            result += 1

    return [result]


# 引数を取得
def get_input_lines():
    line = input()
    N, D = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(N):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['4 5', '0 5', '-2 4', '3 4', '4 -4']
        lines_export = [3]
    if pattern == 2:
        lines_input = ['12 3', '1 1', '1 1', '1 1', '1 1', '1 2', '1 3', '2 1', '2 2', '2 3', '3 1', '3 2', '3 3']
        lines_export = [7]
    if pattern == 3:
        lines_input = ['20 100000', '14309 -32939', '-56855 100340', '151364 25430', '103789 -113141', '147404 -136977', '-37006 -30929', '188810 -49557', '13419 70401', '-88280 165170', '-196399 137941', '-176527 -61904', '46659 115261', '-153551 114185', '98784 -6820', '94111 -86268', '-30401 61477', '-55056 7872', '5901 -163796', '138819 -185986', '-69848 -96669']
        lines_export = [6]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 60132
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxk 100111

typedef long long ll;
typedef long double ld;

int k;
int dp[maxk];
bool used[maxk];
queue<int> q;

int main(){
	scanf("%d", &k);

	memset(dp, 0x3f3f, sizeof(dp));
	for(int i = 1; i <= 9; i++){
		q.push(i);
		dp[i] = i;
	}

	while(!q.empty()){
		int val = q.front();
		q.pop();

		for(int i = 0; i <= 9; i++){
			int v = (val * 10 + i) % k;
			if(dp[v] > dp[val] + i){
				dp[v] = dp[val] + i;
	//			if(!used[v]){
	//				used[v] = 1;
					q.push(v);
			//	}
			}
		}
	//	used[val] = 0;
	}

	printf("%d\n", dp[0]);
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long int llint;

int N;

int main() {
	cin >> N;
	vector<llint> A(N + 1);
	vector<llint> B(N);
	for (int i = 0; i < N + 1; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	llint ans = 0;
	for (int i = 0; i < N; i++) {
		llint num = min(A[i], B[i]);
		ans += num;
		B[i] -= num;
		num = min(A[i + 1], B[i]);
		ans += num;
		A[i + 1] -= num;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
import heapq
import sys
input = sys.stdin.readline
n = int(input())
s = [input() for _ in range(n)]
t = []
p = []
for i in range(n):
    k = 0
    m = 0
    for c in s[i]:
        if c == '(':
            k += 1
        elif c == ')':
            k -= 1
            m = min(k, m)
    if k >= 0:
        t.append((-m, k))
    else:
        k = 0
        m = 0
        for c in s[i][::-1]:
            if c == ')':
                k += 1
            elif c == '(':
                k -= 1
                m = min(k, m)
        p.append((-m, k))
t.sort()
p.sort()
hq = []
hq1 = []
d = 0
idx = 0
for i in range(len(t)):
    while idx < len(t) and d >= t[idx][0]:
        m, k = t[idx]
        heapq.heappush(hq, (-k, m))
        idx += 1
    if hq:
        k, m = heapq.heappop(hq)
    else:
        print('No')
        break
    d -= k
else:
    d1 = 0
    idx = 0
    for i in range(len(p)):
        while idx < len(p) and d1 >= p[idx][0]:
            m, k = p[idx]
            heapq.heappush(hq1, (-k, m))
            idx += 1
            if hq1:
                k, m = heapq.heappop(hq1)
            else:
                print('No')
                break
            d1 -= k
    else:
        if d == d1:
            print('Yes')
        else:
            print('No')


Measured memory_bytes: 212652
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        while(true) {
            int m = stdIn.nextInt();
            int f = stdIn.nextInt();
            int r = stdIn.nextInt();
            if(m == -1 && f == -1 && r == -1)
                break;
            
            if(m + f >= 80) {
                System.out.println("A");
            } else if (m == -1 || f == -1 || m + f < 30) {
                System.out.println("F");
            } else if (m + f >= 65) {
                System.out.println("B");
            } else if (m + f >= 50 || r >= 50) {
                System.out.println("C");
            } else if (m + f >= 30) {
                System.out.println("D");
            } else if (m + f >= 30 || m + f < 50 || r >= 50 ) {
                System.out.println("C");
            }
        }
    }
}


Measured memory_bytes: 26200
# -*- coding: utf-8 -*-
s = raw_input()
lens=len(s)
lenso=lens-1
a=0
if s[0]=="A":
    if ord(s[1])>=0x5B:
            if ord(s[lenso])>=0x5B:
                if s.find("C")>=0:
                    for i in range(2,lens):
                        if ord(s[i])<=0x5B:
                            a=a+1
                    if a==1:
                        print"AC"
                    else:
                        print"WA"
                else:
                    print"WA"
            else:
                print"WA"
    else:
        print"WA"
else:
    print"WA"


Measured memory_bytes: 2568
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <vector>

using namespace std;
using namespace chrono;

#ifdef DEBUG
	//~ #define LOCAL_INPUT_FILE
#else
	//~ #define USE_FILE_IO
#endif

#ifdef USE_FILE_IO
	#define INPUT_FILE "input.txt"
	#define OUTPUT_FILE "output.txt"
	#define cin ____cin
	#define cout ____cout
	ifstream cin(INPUT_FILE);
	ofstream cout(OUTPUT_FILE);
#else
	#ifdef LOCAL_INPUT_FILE
		#define cin ____cin
		ifstream cin("input.txt");
	#endif
#endif

const int infinity = (int)1e9 + 42;
const int64_t llInfinity = (int64_t)1e18 + 256;
const int module = (int)1e9 + 7; 
const long double eps = 1e-8;

mt19937_64 randGen(system_clock().now().time_since_epoch().count());

inline void raiseError(string errorCode) {
	cerr << "Error : " << errorCode << endl;
	exit(42);
}

signed main() {
	#ifndef USE_FILE_IO
		ios_base::sync_with_stdio(false);
	#endif
	string s; cin >> s;
	if (s.size() % 2 != 0) {
		cout << "No" << endl;
		return 0;
	}
	for (int i = 0; i < (int)s.size(); i += 2) {
		if (s[i] != 'h' || s[i+1] != 'i') {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N;
    cin>>N;
    ll count=0;
    rep1(i, N){
        if(i%3!=0 && i%5!=0) count+=i;
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3636
def process(N, A):
    rates = set()
    over_rates = 0
    for a in A:
        a //= 400
        if a < 8:
            rates.add(a)
        else:
            over_rates += 1
    minimum = max(len(rates), 1)
    maximum = len(rates) + over_rates
    return minimum, maximum

N = int(input())
A = map(int, input().split())

minimum, maximum = process(N, A)
print(minimum, maximum)

Measured memory_bytes: 3316
#include<iostream>
#include<string>
using namespace std;

struct Node {
	int key;
    Node *left;
	Node *right;
	Node *parent;
};

Node *root,*NIL;
void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;
   z=new Node;
    
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    
    while (x != NIL) {
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y==NIL){
        root = z;
    }else{
        if(z->key < y->key){
            y->left=z;
        }else {
            y->right = z;
        }
    }
}

void Preparse(Node *T) {
	if (T == NIL) return;
	cout << " " << T->key;
	Preparse(T->left);
	Preparse(T->right);
}
void Inparse(Node *T) {
	if (T == NIL) return;
	Inparse(T->left);
	cout << " " <<T->key;
	Inparse(T->right);
}
int main() {
	int n; cin >> n;
	int num;
  string str;
	for (int i = 0; i < n; i++) {
    cin>>str;
    if(str=="insert"){
      cin>>num;
        insert(num);
      }
    else if(str=="print"){
              Inparse(root);
      cout << endl;
      Preparse(root);
      cout << endl;

    }
  }

	return 0;
}



Measured memory_bytes: 26492
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int main()
{
	int N, A, B;

	scanf("%d %d %d", &N, &A, &B);
	printf("%d\n", min(N*A, B));

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
 
using namespace std;
 
int f1(int x) {
	double v = 0.08 * (double)x;
	int y = v;
	return y;
} 
 
int f2(int x) {
	double v = 0.10 * x;
	int y = v;
	return y;
}

int main() {
	
	ios_base :: sync_with_stdio(0); cin.tie(NULL);
 
	int a, b; cin >> a >> b;

	int mx = max(a, b);

	for(int x = 1; x <= 100000 * mx; ++x) {
		if ((f1(x) == a) && (f2(x) == b)) {
			cout << x << '\n';
			return 0;
		}
	}

	cout << -1 << '\n';


 
	return 0;	
}

Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;

int main(){
	int n , m ; 
	cin >> n >> m ; 
	vector<int> sum(n+2,0);
	for(int i=0;i<m;i++){
		int l , r ; 
		cin >> l >> r ;
		sum[l]+=1 ; 
		sum[r+1]-=1 ; 
	}
	for(int i=1;i<(int)sum.size();i++){
		sum[i] += sum[i-1] ; 
	}
	int ans = 0 ; 		
	for(int i=0;i<(int)sum.size();i++){
		if ( sum[i] == m ) ans++ ; 
	}
	//debug() << imie(sum) ; 
	cout << ans << endl;
    return 0 ;
}


Measured memory_bytes: 640
#include<stdio.h>

int n ,A[100000];
int partition(int p,int r){
int j,x,i,t;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
   
    if(A[j] <= x){
i++;

t=A[i];
A[i]=A[j];
A[j]=t;
    }

}

t=A[i+1];
A[i+1]=A[r];
A[r]=t;

return i+1;
}
int main(){
    int i,count=0,t;

scanf("%d",&n);

for(i = 0 ; i < n ; i++){

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

}
t = partition(0 ,n-1);


for(i = 0 ; i < t ; i++){

    printf("%d ",A[i]);
}
printf("[%d] ",A[t]);
count = t;
for(i=t+1;i<n;i++){
    count++;
printf("%d",A[i]);

if(count != n-1)
printf(" ");

}
printf("\n");

return 0;
}





Measured memory_bytes: 2128
#include <bits/stdc++.h>
using namespace std;
//#define int long long

signed main() {
	int N;
	string S,T,ans;
	cin>>N>>S>>T;
	for(int i=0;i<N;i++){
		ans+=S.at(i);
		ans+=T.at(i);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,d;
int X[20][20];
int main(){
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=d;j++)
			scanf("%d",&X[i][j]);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int sum=0;
			for(int q=1;q<=d;q++)
				sum+=(X[i][q]-X[j][q])*(X[i][q]-X[j][q]);
			double t=sqrt(sum);
			if(t-((int)t)==0)ans++;
		}
	}cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main()
{
    int a ,b , c;
    cin >> a >> b>> c;
    int temp = a;
    a=b;
    b=temp;
    int temp1=a;
    a =c;
    c= temp1;

    cout <<a <<" "<< b<< " "<<c;
    return 0; 
}

Measured memory_bytes: 256
#include <cmath>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

void solve() {
  int n = 3;

  vector<int> a(n);
  for (auto&& i : a)
    cin >> i;

  sort(a.rbegin(), a.rend());

  string f = to_string(a[0]) + to_string(a[1]);

  cout << stoi(f.c_str()) + a[2] << '\n';
}

int main() {
  int t = 1;

#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  t = 3;
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  while (t--)
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
typedef long long ll;

struct UnionFind
{
	vector<int> uni;

	UnionFind(int n) : uni(n, -1) {}
	int root(int a)
	{
		if (uni[a] < 0) return a;
		return uni[a] = root(uni[a]);
	}

	bool connect(int a, int b)
	{
		a = root(a);
		b = root(b);
		if (a == b) return false;
		if (uni[a] > uni[b])
		{
			a ^= b;
			b ^= a;
			a ^= b;
		}
		uni[a] = uni[a] + uni[b];
		uni[b] = a;
		return true;
	}

	bool isConnect(int a, int b)
	{
		return root(a) == root(b);
	}

	int size(int a)
	{
		return -uni[root(a)];
	}
};

signed main(void)
{
	ll n, m;
	cin >> n >> m;
	vector<ll> a(m), b(m), out;
	UnionFind uf(n);
	ll ans;

	rep(i, m) 
	{
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}
	ans = n * (n - 1) / 2;
	for (int i = m - 1; i >= 0; i--)
	{
		out.push_back(ans);
		if (!uf.isConnect(a[i], b[i]))
		{
			ans -= (ll) uf.size(a[i]) * uf.size(b[i]);  
			uf.connect(a[i], b[i]); 
		}
	}
	reverse(out.begin(), out.end());
	rep(i, m)
		cout << out[i] << endl;
	return 0;
}


Measured memory_bytes: 6224
n,t=map(int,input().split())
xList=[]

for i in range(n):
    x,y=map(int,input().split())
    if y<=t:
        xList.append(x)
if len(xList)==0:
    print('TLE')
    exit()

minn=xList[0]
for i in xList:
    if i<minn:
        minn=i

print (minn)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int main()
{
	char a[55][55],b[55][55];
	int f,n,m;cin>>n>>m;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
	for(int i=0;i<m;i++)for(int j=0;j<m;j++)cin>>b[i][j];
	for(int k=0;k<=n-m;k++)
	{
		for(int l=0;l<=n-m;l++)
		{
			f=0;
			for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
				{
					if(a[i+k][j+l]!=b[i][j])
					{
						f=1;
						break;
					}
				}
				if(f==1)break;
			}
			if(f==0)
			{
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
def sub():
    s = input()
    t = input()

    dp_table = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i][j]+1)
            dp_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i+1][j])
            dp_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i][j+1])

    # print(max(dp_table[-1]))
    mem_s = len(s)
    mem_t = len(t)
    ans = ""
    while True:
        if dp_table[mem_s][mem_t] == dp_table[mem_s][mem_t-1]:
            mem_t = mem_t - 1
        elif dp_table[mem_s][mem_t] == dp_table[mem_s-1][mem_t]:
            mem_s = mem_s - 1
        else:
        # if dp_table[mem_s][mem_t] == dp_table[mem_s-1][mem_t-1]:
            ans = s[mem_s-1] + ans
            mem_s = mem_s - 1
            mem_t = mem_t - 1
        if mem_s == 0 or mem_t == 0:
            break
    print(ans)

sub()



Measured memory_bytes: 120412
#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define int long long
const int mod = 1e9 + 7;
inline int ksm(int a, int b)
{
	int ans = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1)
			ans = ans * a % mod;
	return ans;
}

signed main()
{
	io;
	int n;
	int f = 1;
	cin >> n;
	map<int, int> Mp;
	rep(i, 1, n)
	{
		int x;
		cin >> x;
		f &= !Mp[x];
		Mp[x] = 1;
	}
	f ? puts("YES") : puts("NO");

	getchar(); //
	getchar();
}


Measured memory_bytes: 12800
N = int(input())
A = list(map(int, input().split()))


def euclid(v1, v2):
    if v2 == 0:
        return v1
    elif v1 > v2:
        return euclid(v2, v1 % v2)
    else:
        return euclid(v1, v2 % v1)


out = A[0]
for A_i in A[1:]:
    out = euclid(out, A_i)
print(out)


Measured memory_bytes: 14252
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

struct vtx {
  VI edge;
  int color;
};

bool color(vector<vtx> &vs, int x, int c) {
  if(vs[x].color != 0) {
    return vs[x].color != c;
  }
  vs[x].color = c;
  FOR(y, vs[x].edge) {
    if(color(vs, y, 3-c)) {
      return true;
    }
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  ll N, M;
  cin >> N >> M;
  vector<vtx> es(N, {VI(), 0});
  REP(i,0,M) {
    int a, b;
    cin >> a >> b;
    es[a-1].edge.push_back(b-1);
    es[b-1].edge.push_back(a-1);
  }
  ll total = 0;
  if(color(es, 0, 1)) {
    total = N * (N-1) / 2;
  } else {
    int c1 = 0;
    FOR(v,es) {
      if(v.color == 1) {
        c1++;
      }
    }
    total = c1 * (N - c1);
  }
  cout << total - M << endl;

  return 0;
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

struct edge {
    ll to,len;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<edge>> tree(n);
    rep(i,n-1) {
        ll a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        tree[a].pb({b,c});
        tree[b].pb({a,c});
    }
    vector<ll> dist(n,linf);
    vector<bool> seen(n,false);
    int q,k;
    cin >> q >> k;
    k--;
    priority_queue<LP,vector<LP>,greater<LP>> pq;
    pq.push({0,k});
    while(!pq.empty()) {
        auto p = pq.top();
        ll f = p.first,s = p.second;
        pq.pop();
        if(seen[s]) continue;
        seen[s] = true;
        dist[s] = f;
        for(auto e : tree[s]) {
            if(seen[e.to]) continue;
            if(dist[e.to] <= f+e.len) continue;
            pq.push({f+e.len,e.to});
        }
    }
    rep(i,q) {
        int x,y;
        cin >> x >> y;
        x--; y--;
        cout << dist[x]+dist[y] << endl;
    }
}


Measured memory_bytes: 11120
(let* ((n (read))
       (a (make-array (list (1+ n)) :initial-element 0))
       (s (make-array (list (1+ n)) :initial-element 0))
       (r 1000000007)
       (ans 0))
  ;
  (loop :for i :from 1 :to n
        :do (setf (aref a i) (read)))
  (loop :for i :downfrom (1- n) :to 1
        :do (setf (aref s i) (mod (+ (aref s (1+ i)) (aref a (1+ i))) r)))
  ;
  (loop :for i :from 1 :to (1- n)
        :do (setf ans (mod (+ ans (mod (* (aref a i) (aref s i)) r)) r)))
  ;
  (format t "~A~%" ans))


Measured memory_bytes: 80452
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr ll INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1);
constexpr ld EPS = 1e-11;

Vec p, c;

ll solve(ll d, ll g){
	if(g <= 0) return 0;
	if(d == 0) return LINF;

	ll x = solve(d - 1, g);
	ll y = p[d - 1] + solve(d - 1, g - p[d - 1] * d - c[d]);
	ll t = min(p[d - 1] - 1, g / d + !!(g % d));
	ll z = t + solve(d - 1, g - t * d);
	return min({x, y, z});
}

int main(void){
	ll d, g;
	cin >> d >> g;
	g /= 100;
	p.resize(d);
	c.resize(d);
	rep(i, d) cin >> p[i] >> c[i];
	rep(i, d) c[i] /= 100;

	ll max = pow2(d), ans = LINF;
	rep(bit, max){
		bitset<10> bits(bit);
		ll sum = 0, cnt = 0;
		rep(i, d){
			if(bits[i]){
				sum += p[i] * (i + 1) + c[i];
				cnt += p[i];
			}
		}
		repr(i, d){
			if(sum >= g) break;
			if(!bits[i]){
				ll t = (g - sum) / (i + 1) + !!((g - sum) % (i + 1));
				if(t < p[i]) cnt += t;
				else cnt += LINF;
				break;
			}
		}
		chmin(ans, cnt);
	}
	co(ans);

	return 0;
}


Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (unfoldr)

main :: IO ()
main = do
  (n : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    next :: Maybe Digits -> Maybe ([Int], Maybe Digits)
    next = fmap next'
      where
        next' :: Digits -> ([Int], Maybe Digits)
        next' = (,) <$> (0 :) . map snd . reverse <*> succDs
  mapM_ putStrLn . map (map toLEL) . unfoldr next . Just . zeroes $ n

type Digits = [(Int, Int)]

extend :: Digits -> Digits
extend [] = (1, 0) : []
extend ds@((m, k) : _) = (max m (succ k), 0) : ds

zeroes :: Int -> Digits
zeroes 1 = []
zeroes l  = extend . zeroes . pred $ l

succDs :: Digits -> Maybe Digits
succDs [] = Nothing
succDs ((m, k) : ds) | k < m = Just ((m, succ k) : ds)
succDs (_ : ds) = extend <$> succDs ds

showDs :: Digits -> String
showDs = ('a' :) . map (toLEL . snd) . reverse

toLEL :: Int -> Char
toLEL = toEnum . (fromEnum 'a' +)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 2172
a,b,m=map(int, input().split())
list_a=[ int(i)  for i in input().split()]
list_b=[ int(i)  for i in input().split()]
x,y,c=([],[],[])
for i in range(m):
    s=list(map(int, input().split()))
    x+=[s[0]]
    y+=[s[1]]
    c+=[s[2]]
print(min([ list_a[x[i]-1] + list_b[y[i]-1] - c[i]   for i in range(len(c))]+[min(list_a)+min(list_b)]))

Measured memory_bytes: 29044
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
#include <bits/stdc++.h>
using namespace std;
 
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cout_precision cout.setf(ios::fixed); cout.precision(32);
 
using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;
using ld = long double;
 
// ------------------------------------------------------------------------------------------------

ll n, t, m, d, ans;

int main() {
    fast_io; cout_precision;
    cin >> n >> t;
    cin >> m;
    d = INT64_MIN, ans = 0;
    for (ll i = 1, a; i < n; i++) {
        cin >> a;
        if (m > a) {
            m = a;
        } else if (d < a - m) {
            d = a - m;
            ans = 1;
        } else if (d == a - m) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,N = map(int,input().split())
    A = list(map(int,input().split()))

    tot = sum(A)

    if tot >= H:
        res = 'Yes'
    else:
        res = 'No'

    print(res)



main()


Measured memory_bytes: 13272
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  int K;
  cin >> K;

  int an;
  int maxnum=an=max(A,max(B,C));
  int *ma;
  ma = &maxnum;
  for(int i=0;i<K;i++) {
    (*ma)*=2;
  }
  cout << A+B+C-an+maxnum << endl;
}
    


Measured memory_bytes: 256
import kotlin.math.min

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)
fun <T> Array<Array<T>>.print() {
    this.forEach {
        println(it.joinToString(" "))
    }
}

fun main() {
    readInt()
    val x = readIntList()

    var res = Int.MAX_VALUE
    for (p in 1..100) {
        val ps = x.fold(0) { acc, value ->
            acc + (value - p) * (value - p)
        }
        res = min(res, ps)
    }

    println(res)
}


Measured memory_bytes: 36408
#include<stdio.h>
#include<stdlib.h>
struct node {
  int id;
  struct node* next;
};

struct node **list;
int *seq, *group, *stack, counter, phase, except,sp;

void Insert(int, int);
int strongcomponent(int);
int main(void)
{
  int i, v, e,s ,t, q;
  scanf("%d %d", &v, &e);
  list = (struct node**)malloc(sizeof(struct node*) * v);
  seq = (int*)calloc(v, sizeof(int));
  group = (int*)malloc(sizeof(int) * v);
  stack = (int*)malloc(sizeof(int) * v);
  except = v + 1;
  for (i = 0; i < v; i++) {
    list[i] = NULL;
    group[i] = -1;
  }
  for (i = 0; i < e; i++) {
    scanf("%d %d", &s, &t);
    Insert(s,t);
  }
  for (i = 0; i < v; i++) {
    if (!seq[i]) {
      strongcomponent(i);
    }
  }
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d %d", &s, &t);
    if (group[s] == group[t]) printf("1\n");
    else printf("0\n");
  }
  for (i = 0; i < v; i++) free(list[i]);
  free(seq);
  free(group);
  free(stack);
}
void Insert(int a, int b)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->next = list[a];
  list[a] = p;
}
int strongcomponent(int point)
{
  int min;
  struct node *n;
  counter++;
  min = seq[point] = counter;
  stack[sp++] = point;
  for (n = list[point]; n != NULL; n = n->next) {
    int m;
    if (!seq[n->id]) m = strongcomponent(n->id);
    else m = seq[n->id];
    if (m < min) min = m;
  }
  if (min == seq[point]) {
    int x;
    do {
      sp--;
      x = stack[sp];
      group[x] = phase;
      seq[x] = except;
    } while (x != point);
    phase++;
  }
  return min;
}


Measured memory_bytes: 2948
#include <cstdio>
#include <iostream>
typedef long long ll;
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
int aI, aO, aT, aJ, aL, aS, aZ;
int main() {
	aI = Get(), aO = Get(), aT = Get(), aJ = Get(), aL = Get(), aS = Get(), aZ = Get();
	ll ansA = (ll)aO + 2ll * (aI / 2) + 2ll * (aJ / 2) + 2ll * (aL / 2), ansB = 0;
	if (aI && aJ && aL) ansB = (ll)aO + 2ll * ((aI - 1) / 2) + 2ll * ((aJ - 1) / 2) + 2ll * ((aL - 1) / 2) + 3;
	printf("%lld\n", std :: max(ansA, ansB));
	return 0;
}

Measured memory_bytes: 256
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]
for i in range(N+1):
	d[i][i]=0

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


for i in range(1,N+1):
	for j in range(1,N+1):
		for k in range(1,N+1):
			d[i][j]=min(d[i][j], d[i][k]+d[k][j])

for i in range(1,N+1):
	for j in range(1,N+1):
		for k in range(1,N+1):
			d[i][j]=min(d[i][j], d[i][k]+d[k][j])


for i in range(1,N+1):
	for j in range(1,N+1):
		for k in range(1,N+1):
			d[i][j]=min(d[i][j], d[i][k]+d[k][j])


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans
		

Measured memory_bytes: 39836
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
int main() {
	// your code goes here
	string s;
	cin>>s;
	ll out=0;
	ll f=0;
	ll glah=0;
	for(ll i=0;i<s.size();i++)
	{
		//cout<<s[i]<<" "<<out<<" "<<f<<"\n";
		if(s[i]=='B')
		{
			f++;
		}
		else
		{
			out=out+f;
		}
	}
	cout<<out;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	int count1=0,a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n-2;i++)
	{
		if(a[i]>a[i+1]&&a[i+1]>a[i+2])
		count1++;
			if(a[i]==a[i+2]&&a[i+1]>a[i+2])
			count1++;
				if(a[i]<a[i+1]&&a[i+1]<a[i+2])
				count1++;
					if(a[i]==a[i+1]&&a[i+1]>a[i+2])
					count1++;
	}
	cout<<count1;
}

Measured memory_bytes: 256
N = int(input())
W = list(map(int, input().split()))
s1, s2, = 0, 0
ans = 10000000000000000
for i in range(1,N):
  for j in range(N):
    if j<i:
      s1 += W[j]
    else:
      s2 += W[j]
  a = abs(s1 - s2)
  if a < ans:
    ans = a
  s1, s2 = 0, 0

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

int main(){

  int N;
  cin >> N;
  vector<int> a(N), b(N), c(N);
  for(int i=0; i<N; i++){
    cin >> a[i] >> b[i] >> c[i];
  }

  // dp[i,x] = i日目にx=a,b or cを選んだときの，i日目時点の最大値
  map<pair<int,vector<int> *>,int> dp;
  // 1日
  dp[make_pair(0,&a)] = a[0];
  dp[make_pair(0,&b)] = b[0];
  dp[make_pair(0,&c)] = c[0];
  // 遷移
  pair<int,vector<int>*> here;
  pair<int,vector<int>*> next;
  for(int i=0; i<N; i++){
    here = make_pair(i,&a);
    for(auto x : {&b,&c}){
      // i+1日目にxを選ぶ
      next = make_pair(i+1,x);
      dp[next] = max(dp[next],dp[here]+ (*x)[i+1]);
    }

    here = make_pair(i,&b);
    for(auto x : {&c,&a}){
      // i+1日目にxを選ぶ
      next = make_pair(i+1,x);
      dp[next] = max(dp[next],dp[here]+ (*x)[i+1]);
    }

    here = make_pair(i,&c);
    for(auto x : {&a,&b}){
      // i+1日目にxを選ぶ
      next = make_pair(i+1,x);
      dp[next] = max(dp[next],dp[here]+ (*x)[i+1]);
    }
    
  }
  
  cout << max(dp[make_pair(N-1,&a)], max(dp[make_pair(N-1,&b)],dp[make_pair(N-1,&c)])) << endl;

  return 0;
}

Measured memory_bytes: 20224
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#include<set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<n; i++)

const int INF = 1001001001;

void solve(){
  int n, d, a;  cin >> n >> d >> a;
  vector<pair<ll, ll>> mon(n);
  d*=2;
  rep(i, n) {
    int x, h; cin >> x >> h;
    mon[i]=make_pair(x, h);
  }
  sort(mon.begin(), mon.end());
  ll sum = 0;
  ll ans = 0;
  queue<pair<ll, ll>> q;
  rep(i, n){
    ll x = mon[i].first, h = mon[i].second;
    while(q.size() && q.front().first < x){
      sum -= q.front().second;
      q.pop();
    }

    h-=sum;
    if(h>0){
      ll num = (h+a-1)/a;
      ans += num;
      ll damage = num * a;
      sum += damage;
      q.emplace(x+d, damage);
    }
  }

  cout << ans << endl;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <numeric>
#include <iterator>
#include <unordered_map>
#include <array>
#include <map>
#include <cstring>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctgmath>
#include <set>
#include <queue>
#include <fstream>
#include <ostream>
#include <random>
#include <chrono>
using namespace std;
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	string s;
	int k;
	cin >> n >> s >> k;

	k--;
	char c = s[k];

	for (auto i : s)
	{
		if (i != c)
		{
			cout << '*';
		}
		else
		{
			cout << i;
		}
	}
	cout << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T> ostream& operator<<(ostream &os, vector<T> V) {
 os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
	return os << "(" << P.first << "," << P.second << ")";}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif


#define ll long long
#define ld long double
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"

int mod=1e9+7;
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}
inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 

const ll MAX = 403;

int pwr[MAX][MAX];
void pre(){
	ll i,j,k;
	for(i=1;i<MAX;i++){
		for(j=0;j<MAX;j++){
			if(j==0)pwr[i][j] = 1;
			else pwr[i][j] = mul(pwr[i][j-1],i);
		}
	}
	for(j=0;j<MAX;j++){
		for(i=1;i<MAX;i++){
			pwr[i][j] = add(pwr[i][j],pwr[i-1][j]);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	ll n,c;
	cin>>n>>c;
	pre();
	vll A(n),B(n);
	ll i,j,k;
	for(i=0;i<n;i++)cin>>A[i];
	for(i=0;i<n;i++)cin>>B[i];
	vvll dp(2,vll(c+1,0));
	ll prev = 0,cur =1;
	dp[0][0] = 1;
	for(i=0;i<n;i++){
		dp[cur] = vll(c+1,0);
		for(j=0;j<=c;j++){
			for(k=0;k+j<=c;k++){
				ll ab = mul(dp[prev][k] , sub(pwr[B[i]][j],pwr[A[i]-1][j]) );
				// trace(i,j,k,ab);
				dp[cur][j+k] = add(dp[cur][j+k], ab);
			}
		}
		swap(prev,cur);
		// trace(i);
		// for(j=0;j<=c;j++)cout<<dp[prev][j]<<",";
		// cout<<"\n";
	} 
	cout<<dp[prev][c];
}


Measured memory_bytes: 896
import sys; sys.setrecursionlimit(50000)
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

result = []
for x in range(X):
    for y in range(Y):
        if x * y > K: break
        for z in range(Z):
            if x * y * z > K: break
            result.append(A[x]+B[y]+C[z])
result.sort(reverse=True)
for i in range(K):
    print(result[i])


Measured memory_bytes: 112344
#include <stdio.h>
#include <stdlib.h>
int N,X,T,ans,mod;
int main(void) {
	scanf("%d %d %d", &N, &X, &T);

	if(N <= X){
		ans = 1;
	}else{
		mod = N % X;
		if(mod == 0){
			ans = N / X;
		}else{
			ans = ((N - mod) / X) + 1;
		}
	}

	printf("%d", ans*T);

	return 0;
}

Measured memory_bytes: 1732
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, a, b) for (ll i = a; i < b; i++)
#define repr(i, n) for (ll i = n - 1; i >= 0; i--)
#define all(x) x.begin(), x.end()
// #define int ll
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);
const int MOD = 1000000007;
const int MAX = 510000;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n, st = -1;
    ll s[210][210], ans[310], max = -1;
    rep(i, 210) ans[i] = -1;
    map<ll, ll> mp;
    queue<ll> que;
    cin >> n;
    vector<ll> a, c;
    vector<ll> G[300];
    rep(i, n)
    {
        string S;
        cin >> S;
        rep(j, n)
        {
            if (S[j] == '1') {
                s[i][j] = 1;
                G[i + 1].push_back(j + 1);
            } else
                s[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (G[j].size() == i) {
                st = j;
                break;
            }
        }
        if (st != -1)
            break;
    }
    for (int j = 1; j <= n; j++) {
        if (G[j].size() == 1) {
            a.push_back(j);
        }
    }
    if (true) {
        for (int i = 1; i <= n; i++) {

            bool flag = true;
            rep(j, 210) ans[j] = -1;
            que.push(i);
            ans[i] = 1;
            ll max1 = -1;
            while (!que.empty()) {
                int i = que.front();
                que.pop();
                for (int j : G[i]) {
                    if (ans[j] != -1) {
                    } else {
                        ans[j] = ans[i] + 1;
                        max1 = std::max(max1, ans[j]);
                        que.push(j);
                    }
                }
            }
            for (int i = 1; i < n + 1; i++) {
                for (int j : G[i]) {
                    if (ans[i] != ans[j] + 1 && ans[i] != ans[j] - 1) {
                        flag = false;
                    }
                }
            }
            if (flag)
                max = std::max(max, max1);
        }
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 640
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

class AtCoder
{
    const int MOD = 1000000007;
    public void Slove()
    {
        int[] dp = new int[13];
        int[] mod = Enumerable.Range(0, 140).Select(x => x % 13).ToArray();
        dp[0] = 1;
        foreach(char c in Console.ReadLine())
        {
            int[] temp = new int[13];
            if(c == '?')
            {
                for(int j = 0; j < 10; j++)
                {
                    for (int i = 0, v = j; i < 13; i++, v += 10)
                    {
                        temp[mod[v]] += dp[i];
                        temp[mod[v]] %= MOD;
                    }
                }
            }
            else
            {
                for(int i = 0, v = int.Parse(c.ToString());i < 13; i++, v+=10)
                {
                    temp[mod[v]] += dp[i];
                    temp[mod[v]] %= MOD;
                }
            }
            dp = temp;
            //Console.WriteLine(string.Join(" ", dp));
        }
        Console.WriteLine(dp[5]);
    }
    static void Main()
    {
        var ac = new AtCoder();
        ac.Slove();
    }
}

Measured memory_bytes: 17624