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

#define M 1000000007

long long modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}

long long f[200100], g[200100];
int s[200100];
vector<int> adj[200100];

void dfs(int i, int p) {
    int ssum = 0;
    for (int j : adj[i]) {
        if (j != p) { dfs(j, i); ssum += s[j]; }
    }
    long long fval = 0, gval = 0;
    fval = gval = modexp(2, ssum, M) - 1;
    for (int j : adj[i]) {
        fval += f[j] - modexp(2, s[j], M) + 1
            + g[j] * (modexp(2, ssum - s[j] + 1, M) - 1);
        gval += g[j] * modexp(2, ssum - s[j] + 1, M);
        fval %= M; gval %= M;
    }
    f[i] = fval;
    g[i] = gval;
    s[i] = 1 + ssum;
}

int main() {
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0, -1);
    cout << (f[0] * modexp((M+1)/2, s[0], M) % M + M) % M << endl;
}


Measured memory_bytes: 28416
h,w,p = list(map(int,input().split()))
l = [list(input()) for _ in range(h)]

ans=0
for i in range(2**h):
    h_i = bin(i)
    h_i = ("0"*(h-len(h_i)+2))+h_i[2:]
    for j in range(2**w):
        w_i = bin(j)
        w_i = ("0"*(w-len(w_i)+2))+w_i[2:]
        cnt=0
        for k in range(h):
            if h_i[k]=="1":
                continue
            for m in range(w):
                if w_i[m]=="1":
                    continue
                if l[k][m]=="#":
                    cnt+=1
        if cnt==p:
            ans+=1
print(ans)

Measured memory_bytes: 9232
n = input()
n_list = [i for i in n]
n_len = int(len(n))
for j in range(n_len):
  if j % 2 == 0 and n_list[j] == "L":
    print("No")
    break
  if j % 2 == 1 and n_list[j] == "R":
    print("No")
    break
else:
    print("Yes")

Measured memory_bytes: 3060
red, green, blue, total = map(int, input().split(' '))

available_balls = [red, green, blue]
available_balls.sort(reverse=True)

num_combination = 0
for zero in range(0, (total // available_balls[0]) + 1):
    mod_ball = total - zero * available_balls[0]
    for one in range(0, (mod_ball // available_balls[1]) + 1):
        rest_ball = mod_ball - one * available_balls[1]
        
        if rest_ball % available_balls[2] == 0:
            num_combination += 1
            
        # if rest_ball % available_balls[2] == 0:
        #     two = rest_ball // available_balls[2]
        #     print(f"({zero}, {one}, {two}) == OK!")
        #     num_combination += 1
        # else:
        #     two = rest_ball // available_balls[2]
        #     print(f"({zero}, {one}, {two}) -- NG")

print(num_combination)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int32_t main(){
	IOS;
	string s;
	cin >> s;
	int cnt =0, ok =0;
	int n = s.size();
	for(int i =0; i<n; ++i){
		if(s[i] == 'R'){
			for(int j = i; j<n; ++j){
				if(s[j] == 'R'){
					cnt++;
					ok =1;
				}
				else break;
			}
		}
		if(ok) break;
	}
	cout << cnt;

	return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
const ll longinf=1ll<<60;
const int inf=(1<<30)-1;

int main(){
      int a[5];
      rep0(i,5){
            cin>>a[i];
      }
      ll ans=0;
      rep0(i,5){
            ans+=(((a[i]+9)/10)*10);
      }
      int pos=10;
      rep0(i,5){
            if(a[i]%10>0){
                  pos=min(a[i]%10,pos);
            }
      }
      cout<<ans-(10-pos)<<endl;
      return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(500*500)
n = int(input())
a = [[] for _ in range(n)]; b = [-1]*n; b[0] = 0
for i in range(n-1):
    u, v, w = map(int, input().split())
    a[u-1].append([v-1, w]); a[v-1].append([u-1, w])
def dfs(A, k):
    for i in A[k]:
        if b[i[0]] == -1:
            b[i[0]] = b[k]+i[1]
            dfs(A, i[0])
dfs(a, 0)
for i in b:
    print(0) if i%2 == 0 else print(1)

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ a>b?:a=b; }
template<class T> void chmin(T& a, T b){ a<b?:a=b; }

int main() {
    string s, t;
    cin >> s >> t;
    if (s == t.substr(0, t.size() - 1))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define rd(x) cin >> x;
#define rda(a,n) for(int i=1;i<=n;i++) cin >> a[i];
#define wr(x) cout << x << ' ';
#define wrl(x) cout << x << '\n';
#define wra(a,n) for(int i=1;i<=n;i++) cout << a[i] << ' '; cout << '\n';
#define lg length()
#define pb(x) push_back(x)
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
struct comp{
    bool operator()(long long a, long long b){
        return a>b;
    }
};

int n,t,x=1e9,a[100005];
bool p=1;

int main(){
    ios_base :: sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i],x=min(a[i],x);
    for(int i=1;i<=n;i++){
        if(a[i]==x+1) p=0;
        else if(a[i]==x) t++;
        else{
            cout << "No";
            return 0;
        }
    }
    if(p){
        if(2*x<=n || x==n-1) cout << "Yes";
        else cout << "No";
    }
    else{
        if(2*x<=n+t-2 && x>=t) cout << "Yes";
        else cout << "No";
    }
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
char s;
int ans=0;
int main()
{
    cin>>s;
    if(s!='C')ans++;
    cin>>s;
    if(s!='O')ans++;
    cin>>s;
    if(s!='D')ans++;
    cin>>s;
    if(s!='E')ans++;
    cin>>s;
    if(s!='F')ans++;
    cin>>s;
    if(s!='E')ans++;
    cin>>s;
    if(s!='S')ans++;
    cin>>s;
    if(s!='T')ans++;
    cin>>s;
    if(s!='I')ans++;
    cin>>s;
    if(s!='V')ans++;
    cin>>s;
    if(s!='A')ans++;
    cin>>s;
    if(s!='L')ans++;
    cin>>s;
    if(s!='2')ans++;
    cin>>s;
    if(s!='0')ans++;
    cin>>s;
    if(s!='1')ans++;
    cin>>s;
    if(s!='6')ans++;
    cout<<ans;
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

class Prints {
private:
    class __Prints {
    public:
        __Prints(const char* sep, const char* term) : sep(sep), term(term) {}
        template <class... Args>
        void operator()(Args&&... args) const { print(std::forward<Args>(args)...); }

    private:
        const char *sep, *term;
        void print() const { std::cout << term; }
        void print_rest() const { std::cout << term; }
        template <class T, class... Tail>
        void print(T&& head, Tail&&... tail) const { std::cout << head, print_rest(std::forward<Tail>(tail)...); }
        template <class T, class... Tail>
        void print_rest(T&& head, Tail&&... tail) const { std::cout << sep << head, print_rest(std::forward<Tail>(tail)...); }
    };

public:
    Prints() {}
    __Prints operator()(const char* sep = " ", const char* term = "\n") const { return __Prints(sep, term); }
    template <class T>
    void print_vec(const std::vector<T>& vec, const char* sep = " ", const char* term = "\n") const {
        const size_t sz = vec.size();
        for (size_t i = 0; i < sz; i++) std::cout << vec[i] << (i == sz - 1 ? term : sep);
    }
};

Prints prints;

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N, K;
    cin >> N >> K;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll left = 0, right = 1001001001ll;
    while (right - left > 1) {
        ll mid = (left + right) >> 1;
        ll cnt = 0;
        for (ll i = 0; i < N; i++) {
            ll x = (A[i] + mid - 1) / mid;
            cnt += x - 1;
        }
        if (cnt <= K) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    prints()(right);
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    cout << setprecision(18) << fixed;
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 4640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;


#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pii pair<int,int>
#define pf push_front
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<pii>
#define pqsmall priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define spitr set<pii>:: iterator
#define mitr map<string,int>:: iterator

int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}

typedef tree<pii, null_type, less<pii>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;

#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

const int N=2e3+5;
int freq[N];

int32_t main()
{
    fast;
    int n,x,y;cin>>n>>x>>y;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(i==x and j==y)
                freq[1]++;
            else if(i>=x and i<=y and j>=x and j<=y)
            {
                int val=min(j-i,i-x+1+y-j);
                freq[val]++;
            }
            else if(i<=x and j<=x)
                freq[j-i]++;
            else if(i>=y and j>=y)
                freq[j-i]++;
            else if(i<=x and j>=y)
                freq[x-i+j-y+1]++;
            else if(i<=x and j<=y)
            {
                int val=x-i;
                val+=min(j-x,1+y-j);
                freq[val]++;
            }
            else
            {
                int val=j-y;
                val+=min(y-i,i-x+1);
                freq[val]++;
            }
        }
    }

    for(int i=1;i<n;i++)
        cout<<freq[i]<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long INF = 1LL << 60;
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int N, K;
  string S; 
  cin >> N >> S >> K;
  char C = S.at(K - 1);
  
  for (int i = 0; i < N; i++)
  {
    if (S.at(i) == C) cout << S.at(i);
    else cout << '*';
  }
  cout << endl;
}

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

int n,k;
int a[100010],pw[100010],rev[100010];

inline int my_pow(int x,int y)
{
  if(y==0) return 1;
  if(y==1) return x;
  int res=my_pow(x,y/2);
  if(y%2==0) return (res*res)%INF;
  else return (((res*res)%INF)*x)%INF;
}

signed main()
{
  ios::sync_with_stdio(false);
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+n+1);
  pw[0]=1;rev[0]=1;
  for(int i=1;i<=n;i++){
    pw[i]=(pw[i-1]*i)%INF;
    rev[i]=my_pow(pw[i],INF-2ll);
  }
  int ans=0ll;
  for(int i=1;i<=n-k+1;i++){
    int val=pw[n-i]*rev[n-i-k+1];
    val%=INF;
    val*=rev[k-1];val%=INF;
    val*=a[i];val%=INF;
    ans-=val;
  }
  for(int i=k;i<=n;i++){
    int val=pw[i-1]*rev[i-k];
    val%=INF;
    val*=rev[k-1];val%=INF;
    val*=a[i];val%=INF;
    ans+=val;
  }
  ans%=INF;
  if(ans<0) ans+=INF;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int x, n;
    cin >> x >> n;
    vector<int> data(101);
    for (int i = 0; i < n; i++)
    {
        int dataa;
        cin >> dataa;
        data[dataa] = 1;
    }
    bool sig = true;
    bool found = false;
    int num = 0;
    while (!found)
    {
        int now = sig ? x + num : x - num;
        bool include = false;
        if (data[now])
            include = true;
        if (include == false)
        {
            cout << now << endl;
            return 0;
        }
        sig = !sig;
        if (sig == false)
            num++;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<62;
const int IINF = 1000000000;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;


ll gcd(ll x, ll y){
    if (y==0) return x;
    else return gcd(y, x%y);
}


vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(){
    ll N; cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }

    vector<ll> counter(10000005, 0);
    bool isOK = true;
    rep(i,N){
        vector<pair<ll,ll>> pfs = prime_factorize(A[i]);
        for (auto pf : pfs) {
            if (counter[pf.first] > 0){
                isOK = false;
                break;
            }
            counter[pf.first]++;
        }
    }

    if (isOK){
        cout << "pairwise coprime" << endl;
    }
    else{
        ll entire_gcd = A[0];
        for(int i = 1; i < N; i++){
            entire_gcd = gcd(entire_gcd, A[i]);
        }

        if (entire_gcd == 1){
            cout << "setwise coprime" << endl;
        }
        else{
            cout << "not coprime" << endl;
        }
    }
}


Measured memory_bytes: 89244
import math

class Point:

    def __init__(self,x,y):
        self.x=x
        self.y=y
    

def kock(n,p1,p2):
    if n==0:
        return
    
    #calculate s,t,u from p1 and p2
    sx=(2*p1.x+1*p2.x)/3
    sy=(2*p1.y+1*p2.y)/3
    s=Point(sx,sy)
    tx=(1*p1.x+2*p2.x)/3
    ty=(1*p1.y+2*p2.y)/3
    t=Point(tx,ty)
    ux=(tx-sx)*math.cos(math.pi/3)-(ty-sy)*math.sin(math.pi/3)+sx
    uy=(tx-sx)*math.sin(math.pi/3)+(ty-sy)*math.cos(math.pi/3)+sy
    u=Point(ux,uy)

    kock(n-1,p1,s)
    print('{:.8f}'.format(s.x),'{:.8f}'.format(s.y))
    kock(n-1,s,u)
    print('{:.8f}'.format(u.x),'{:.8f}'.format(u.y))
    kock(n-1,u,t)
    print('{:.8f}'.format(t.x),'{:.8f}'.format(t.y))
    kock(n-1,t,p2)

p1=Point(0,0)
p2=Point(100,0)


n=int(input())
print('{:.8f}'.format(p1.x),'{:.8f}'.format(p1.y))
kock(n,p1,p2)
print('{:.8f}'.format(p2.x),'{:.8f}'.format(p2.y))


Measured memory_bytes: 5820
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

lint lcm(lint a, lint b) {
    return (a / gcd(a, b)) * b;
}

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

// vars
int n, k;
vector<int> d;
vector<vector<int>> a;

void input(){
    cin >> n >> k;
    d.resize(k);
    a.resize(k);
    REP(i, k){
        cin >> d[i];
        a[i].resize(d[i]);
        REP(j, d[i]){
            cin >> a[i][j];
            a[i][j]--;
        }
    }
}

void solve(){
    vector<int> snuke(n, 0);
    //cout << endl;
    REP(i, k){
        REP(j, d[i]){
            //cout << a[i][j] << " ";
            snuke[a[i][j]] = 1;
        }
        //cout << endl;
    }
    int ans = 0;
    REP(i, n){
        if(snuke[i] == 0){
            ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

Measured memory_bytes: 3200
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val writer = new java.io.PrintWriter(System.out)
    writer.println(solve(sc))
    writer.flush()
  }

  def solve(sc: Scanner): String = {
    val (a, p) = (sc.nextInt(), sc.nextInt())
    val cuts = a * 3 + p
    scala.math.floor(cuts / 2).toInt.toString
  }

  private def debug(x: Any): Unit = {
    if (System.getenv("LOCAL_DEBUG") != null) println(x)
  }
}


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

vector<vector<int> > initDP(vector<vector<int> > DP, int N, int W)
{
  for (int i = 0; i <= W; i++)
  {
    DP.at(0).at(i) = 0;
  }
  for (int i = 0; i <= N; i++)
  {
    DP.at(i).at(0) = 0;
  }
  return DP;
}

int main()
{
  int N, W, v, w, use, skip;
  cin >> N >> W;
  vector<pair<int, int> > items(N + 1);
  vector<vector<int> > DP(N + 1, vector<int>(W + 1));

  for (int i = 1; i <= N; i++)
  {
    cin >> v >> w;
    items.at(i) = make_pair(v, w);
  }
  DP = initDP(DP, N, W);
  for (int n = 1; n <= N; n++)
  {
    for (int w = 1; w <= W; w++)
    {
      if (items.at(n).second <= w)
      {
        use = items.at(n).first + DP.at(n - 1).at(w - items.at(n).second);
        skip = DP.at(n - 1).at(w);
        DP.at(n).at(w) = max(use, skip);
      }
      else
      {
        DP.at(n).at(w) = DP.at(n - 1).at(w);
      }
    }
  }
  cout << DP.at(N).at(W) << endl;
}


Measured memory_bytes: 14684
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int answer = 0;
		for (int i = 0; i < n; i++) {
			if (sc.nextInt() >= k) answer++;
		}
		System.out.println(answer);
	}
}


Measured memory_bytes: 47996
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

int gcd(int a, int b){
    return( a ? gcd(b%a,a):b);
}

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> left(n);
    vector<int> right(n);
    rep(i,n){
        cin >> a[i];
    }
    left[0]=a[0];
    right[n-1]=a[n-1];
    for(int i=1;i<n;i++){
        left[i] = gcd(left[i-1],a[i]);
        right[n-1-i] = gcd(right[n-i],a[n-1-i]);
    }
    int ans = max(right[1],left[n-2]);
    for(int i=1;i<n-1;i++){
        ans = max(ans,gcd(left[i-1],right[i+1]));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4520
#python

N = input()
a = []
for i in range(N):
    a.append(input())

sum=sum(a)

if sum%10!=0:
	print sum
else:
	a.sort()
	#print a
	for num in a:
		if num%10!=0:
			print sum-num
			break
	else:
		print 0

Measured memory_bytes: 2568
n,k=gets.split.map(&:to_i)
xs=gets.split.map(&:to_i).push(0).sort
min=10**9
(n-k+1).times do |i|
  right=xs[i+k]
  left=xs[i]
  if right*left<0
    cur=right.abs+left.abs+[right.abs,left.abs].min
  else
    cur=[right.abs,left.abs].max
  end
  min=cur if min>cur
end
puts min


Measured memory_bytes: 11896
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll k,a,b;

int main(){
    scanf("%lld%lld%lld",&k,&a,&b);

    if (b - a <= 2){
        printf("%lld\n", k+1);
    } else {
        if (k+1 < a){
            printf("%lld\n", k+1);
        }
        else {
            printf("%lld\n", (k+1-a)/2 * (b-a) + (k+1-a)%2 + a);
        }
    }
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e12;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n + 1, 0);
  FOR(i, 1, n + 1) {
    cin >> a[i];
    a[i] += a[i - 1];
  }

  ll ans = INF;
  FOR(i, 1, n) {
    ll res = a[n] - 2 * a[i];
    if (res < 0) res = -res;
    ans = min(ans, res);
  }
  cout << ans << endl;



  
  return 0;
}

Measured memory_bytes: 1792
# D

N = int(input())
# import sympy
# factors = sympy.factorint(N)

# https://note.nkmk.me/python-prime-factorization/
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import collections
factors = dict(collections.Counter(prime_factorize(N)))

num = 0
for f in factors.keys():
    size = 1
    while factors[f] >= size:
        factors[f] -= size
        num += 1
        size += 1

print(num)

Measured memory_bytes: 9460
//gauravsinghh
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 999999999999999999
#define siz 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define ffo(i, a, b) for(int i = a; i >= b; i--)
#define MAX 100005
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

bool comp(const pair < ll, ll >&a, const pair < ll, ll >&b){
    return ((a.ss < b.ss) || (a.ss == b.ss && a.ff < b.ff));
}

ll func(ll n){
    ll c = 0;
    if(n%2 == 0){
        while(n%2 == 0){
            n /= 2;
            c++;
        }
    }
    return c;
}

signed main(){ 
    IOS
    //io_set();
    ll n, s = 0, x;
    cin >> n;
    rep(i, n){
        cin >> x;
        s += func(x);
    }
    cout << s << endl;
    return 0;
}



Measured memory_bytes: 256
def inp():
  return list(input())

N = int(input())
res = {}

for i in range(N):
  s = str(sorted(inp()))
  
  if s in res:
    res[s] += 1
  else:
    res[s] = 1
    

ans = 0
for num in res.values():
  ans += num*(num-1)/2
  
print(int(ans))

Measured memory_bytes: 21988
//============================================================================
// 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

//============================================================================
#define PI 3.14159265359
#define succ(x) ((x)+1)
#define pred(x) ((x)-1)
//============================================================================
void enter()
{
    int x,y,i,j,s;

    while(1){
        scanf("%d", &y);
        scanf("%d", &x);
        if (!x && !y)
            return;
        for (i=s=0; i<y; i++, s^=1){
            for (j=0; j<x; j++)
                printf("%c", ((j&1)^s == 0)?'#':'.');
            printf("\n");
        }
        printf("\n");
    }
}
//============================================================================
int main(void)
{
    enter();
    return 0;
}
//============================================================================

Measured memory_bytes: 572
using System;

namespace ABC166B
{
    class Program
    {
        static void Main(string[] args)
        {
            var target = Console.ReadLine().Split(' ');
            int N = int.Parse(target[0]);
            int K = int.Parse(target[1]);
            int[] x = new int[N];
            for(int i=0;i<K;i++){
                int d = int.Parse(Console.ReadLine());
                target = Console.ReadLine().Split(' ');
                for(int j=0; j<d;j++){
                    x[int.Parse(target[j])-1]++;
                }
            }
            int count = 0;
            for(int i=0;i<N;i++){
                if(x[i] == 0) count++;
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 27864
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
const int MAX_N = 200005;
struct edge{ int to, cost; };
const int INF = 1001001001;
const int MAX_V = 2005;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
    // greater<P>を指定することでfirstが小さい順に取り出せるようにする
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+MAX_V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        for(int i=0; i<G[v].size(); i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;
    rep(i,n-1){
        int from,to,cost;
        from = i; to = i + 1;
        cost = 1;
        edge e1, e2;
        e1.to = to; e1.cost = cost;
        e2.to = from; e2.cost = cost;
        G[from].push_back(e1);
        G[to].push_back(e2);
    }
    edge e1, e2;
    e1.to = y; e1.cost = 1;
    e2.to = x; e2.cost = 1;
    G[x].push_back(e1);
    G[y].push_back(e2);

    int f[n] = {};
    rep(i,n){
        dijkstra(i);
        srep(j,i+1,n)f[d[j]]++;
    }

    srep(i,1,n)cout << f[i] << endl;
    return 0;
}

Measured memory_bytes: 384
s = gets.chop
X, Y = gets.split.map &:to_i

a, *b = s.split ?T
if a.nil?
  puts X == 0 && Y == 0 ? :Yes : :No
  exit
end
xs, ys = b.map(&:size).partition.with_index{|_,i|i.odd?}
x = y = 0
x += a.size
# p [xs, ys]
# p [x,y]

def f(a, first, goal)
  q = {}
  q[first] = 1
  a.each{|n|
    next_q = {}
    q.each{|x,_|
      next_q[x + n] = 1
      next_q[x - n] = 1
    }
    q = next_q
  }
  q.keys.include? goal
end

puts f(xs, x, X) && f(ys, y, Y) ? :Yes : :No


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

signed main(){

  string s;
  cin>>s;

  auto ok = [](string const& s){
    int n = s.size();
    int m = n/2;
    if(m*2!=n)return false;
    return s.substr(0,m)==s.substr(m);
  };

  while(1){
    s.pop_back();
    if(ok(s)){
      cout<<s.size()<<endl;
      return 0;
    }
  }

}

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

using namespace std;

int main(void) {
    while(true) {
        int n, m;
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        vector<int> win(n, 0), lose(n, 0);
        for(int i = 0; i < m; i++) {
            int s, k;
            cin >> s >> k;
            if(k == 1) {
                int c;
                cin >> c;
                lose[c - 1] += s;
                win[c - 1] += s;
            }
            else {
               for(int j = 0; j < k; j++) {
                   int c;
                   cin >> c;
                   win[c - 1] += s;
                }
            }
        }
    
        int fmin = INT_MAX, smin = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(fmin > lose[i]) {
                smin = fmin;
                fmin = lose[i];
            }
            else if(smin > lose[i]) smin = min(smin, lose[i]);
        }
        int ans = -1;
        for(int i = 0; i < n; i++) {
            int diff = win[i] - (lose[i] == fmin ? smin : fmin);
            ans = max(ans, diff + 1);
        }
            cout << ans << "\n";
    }
    return 0;
}



Measured memory_bytes: 3164
#include "bits/stdc++.h"

using namespace std;

static const int maxn = 6e3 + 5;

struct State
{
      int len;
      int link;
      map <char, int> Next;

      State() {}

      void clean()
      {
            len = 0;
            link = -1;
            Next.clear();
      }
} st[maxn * 2];

int sz;
int last;

void init()
{
      sz = 0;
      last = 0;
      for (int i = 0; i < maxn * 2; i++) st[i].clean();
      sz++;
}

void SAM(char ch)
{
      int cur = sz++;
      st[cur].len = st[last].len + 1;
      int p;
      for (p = last; p != -1 && !st[p].Next.count(ch); p = st[p].link)
      {
            st[p].Next[ch] = cur;
      }
      if (p == -1)
      {
            st[cur].link = 0;
      }
      else
      {
            int q = st[p].Next[ch];
            if (st[p].len + 1 == st[q].len)
            {
                  st[cur].link = q;
            }
            else
            {
                  int clone = sz++;
                  st[clone].len = st[p].len + 1;
                  st[clone].Next = st[q].Next;
                  st[clone].link = st[q].link;
                  for ( ; p != -1 && st[p].Next[ch] == q; p = st[p].link)
                  {
                        st[p].Next[ch] = clone;
                  }
                  st[q].link = st[cur].link = clone;
            }
      }
      last = cur;
}

int main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);


      int len;
      string s;
      cin >> len >> s;
      init();
      int maxi = 0;
      for (int i = 0; i < len; i++)
      {
            int root = 0;
            int cnt = 0;
            int j = i;
            while (j < len)
            {
                  char ch = s[j];
                  if (st[root].Next.count(ch) == 0) break;
                  root = st[root].Next[ch];
                  j++;
                  cnt++;
            }
            maxi = max(maxi, cnt);
            SAM(s[i]);
      }
      cout << maxi << '\n';
}


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

using namespace std;

typedef long long int ll;

const int mod = 1e9 + 7;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);

  int n, k;
  cin >> n >> k;
  vector < pair < int, int > > v;
  bool ok = false;
  int cnt_zero = 0;
  for (int i = 0; i < n; i++) {
    int a; cin >> a;
    ok |= (a > 0);
    if (a > 0) v.push_back({a, 1});
    else if (a < 0) v.push_back({-a, -1});
    else cnt_zero++;
  }

  if (n - cnt_zero < k) {
    cout << 0 << '\n';
    return 0;
  }

  sort (v.begin(), v.end(), greater < pair < int, int > > ());

  int cnt = 0;
  for (int i = 0; i < k; i++) {
    cnt += (v[i].second == -1);
  }

  if (!ok && k & 1) {
    // number is -ve.
    if (cnt_zero) cout << 0 << '\n';
    else {
      reverse (v.begin(), v.end());
      ll ans = 1;
      for (int i = 0; i < k; i++) ans = (ans * v[i].first) % mod;
      ans = mod - ans;

      cout << ans << '\n';
    }
  } else {
    // number is +ve.
    if (cnt & 1) {
      int idx_last_neg = -1, idx_last_pos = -1;
      for (int i = 0; i < k; i++) {
        if (v[i].second == 1) idx_last_pos = i;
        else idx_last_neg = i;
      }

      if (idx_last_pos == -1) {
        // k is odd, and +ve number is ahead.
        for (int i = k; i < n; i++) {
          if (v[i].second == 1) {
            swap (v[i], v[idx_last_neg]);
            ok = false;
            break;
          }
        }
      } else if (k == n) {
        ll ans = 1;
        for (int i = 0; i < k; i++) ans = (ans * v[i].first) % mod;
        ans = mod - ans;
        cout << ans << '\n';
        return 0;
      } else {
        int i = -1, j = -1;
        for (int p = k; p < n; p++) {
          if (v[p].second == -1 && j == -1) j = p;
          if (v[p].second == 1 && i == -1) i = p;
        }

        if (i == -1) swap (v[j], v[idx_last_pos]);
        else if (j == -1) swap (v[i], v[idx_last_neg]);
        else {
          if ((ll)v[i].first * v[idx_last_pos].first > (ll)v[j].first * v[idx_last_neg].first) swap (v[i], v[idx_last_neg]);
          else swap (v[j], v[idx_last_pos]);
        }
      }
    }

    ll ans = 1;
    for (int i = 0; i < k; i++) ans = (ans * v[i].first) % mod;
    cout << ans << '\n';
  }
}


Measured memory_bytes: 5316
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <list>

using namespace std;

int main(int argc, char * argv [] )
{
    string str;
    cin >> str;
    int n;
    cin >> n;

    int strSize = str.size();
    for (int i = 0; i < strSize; ++i) {
        char ch = str.at(i);
        int dist = 'z' - ch + 1;

        if (i != strSize - 1) {
            if (ch == 'a') {
                cout << ch;
            } else if (n >= dist) {
                cout << 'a';
                n -= dist;
            } else {
                cout << ch;
            }
        } else {
            if (n < dist) {
                ch += n;
            } else {
                ch = 'a' + (n - dist) % 26;
            }
            cout << ch;
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#define STORE 5
struct SoldQuantity {
	int am_quantity;
	int pm_quantity;
	int total_quantity;
};

int main(void){
	struct SoldQuantity data[STORE];
	char str[] = { 'A','B','C','D','E' };
	int i,flag,max,max_index=0;

	while (1) {
		flag = 0;
		max = 0;
		for (i = 0; i < STORE; i++) {
			scanf("%d %d",&data[i].am_quantity, &data[i].pm_quantity);
			if (data[0].am_quantity == 0 && data[0].pm_quantity == 0) {
				flag = 1;
				break;
			}
			data[i].total_quantity = data[i].am_quantity + data[i].pm_quantity;
		}
		if (flag)break;
		for (i = 0; i < STORE; i++) {
			if (max < data[i].total_quantity) {
				max = data[i].total_quantity;
				max_index = i;
			}
		}
		printf("%c %d\n",str[max_index],max);
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, d, a;

struct LazySegmentTree {
private:
	int n;
	vector<ll> node, lazy;

public:
	LazySegmentTree(vector<ll> v) {
		int sz = (int)v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, 0);

		for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
	}

	void eval(int k, int l, int r) {
		if (lazy[k] != 0) {
			node[k] += lazy[k];
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k] / 2;
				lazy[2 * k + 2] += lazy[k] / 2;
			}
			lazy[k] = 0;
		}
	}

	void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		eval(k, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] += (r - l) * x;
			eval(k, l, r);
		}
		else {
			add(a, b, x, 2 * k + 1, l, (l + r) / 2);
			add(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = node[2 * k + 1] + node[2 * k + 2];
		}
	}

	ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		eval(k, l, r);
		if (b <= l || r <= a) return 0;
		if (a <= l && r <= b) return node[k];
		ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
		ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
		return vl + vr;
	}
};


ll ans = 0;
int main() {
	cin >> n >> d >> a;
	vector<P> s(n);
	REP(i, n)cin >> s[i].first >> s[i].second;
	sort(ALL(s));
	vector<ll> z(n);
	REP(i, n)z[i] = s[i].first;
	z.push_back(INF);
	LazySegmentTree seg(vector<ll>(n + 100, 0));
	REP(i, n) {
		seg.add(i, i + 1, s[i].second);
	}
	REP(i, n) {
		ll now = seg.getsum(i, i + 1);
		if (now <= 0)continue;
		ll b = upper_bound(ALL(z), z[i] + 2 * d) - z.begin();
		ll cnt = (now + a - 1) / a;
		ans += cnt;
		seg.add(i, b, cnt * a * -1);
	}
	cout << ans << endl;
}


Measured memory_bytes: 16100
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

long long num[100010];

int main()
{
    for(long long i=1;i<100010;i++)
        num[i]=i*i;
    long long N;
    while(cin >> N)
    {
        int tp=upper_bound(num,num+100010,N)-num;
        cout << num[tp-1] << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>
int main()
{
    unsigned long long int a, b;
    scanf("%lld %lld", &a, &b);
    a--;
    if (a % 4 == 1)a = 1;
    else if (a % 4 == 2)a = a + 1;
    else if (a % 4 == 3)a = 0;
    if (b % 4 == 1)b = 1;
    else if (b % 4 == 2)b = b + 1;
    else if (b % 4 == 3)b = 0;
    printf("%lld\n", a^b);
    return 0;
}

Measured memory_bytes: 128
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned int  ull;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define int ll
#define pll pair<ll, ll> 
#define pdd pair<ld, ld> 
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 1000000007
using namespace std;

ll power(ll x, ll y){  
	if(x == 1 || y == 0)
		return 1;
    ll res = 1;   
    x = x % mod; 
    if (x == 0) 
		return 0;  
    while (y > 0){  
        if (y & 1)  
	        res = (res * x) % mod;  
        y = y >> 1; 
        x = (x * x) % mod;  
    }  
    return res;  
} 
vi pr;
void sieve(int n){ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++){ 
        if (prime[p] == true){ 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 

    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          pr.pb(p); 
} 
int dp[20001];
int solve(int s){
	if(s == 0)
		return 1;
	if(dp[s] != -1)
		return dp[s];
	int so = 0;
	for(int i = 3; i <= s; i++){
		if(s - i >= 0){
			so = (so + solve(s - i)) % mod;
		}
	}
	return dp[s] = so;
}

signed main(){
	FASTIO
	int s;
	cin >> s;
	for(int i = 0; i <= s; i++)
		dp[i] = -1;
	cout << solve(s);
    return 0;
}


Measured memory_bytes: 3680
use std::io::{self, BufRead};

fn main() {
    let si = io::stdin();
    let l = si.lock().lines().next().unwrap().unwrap();
    let mut ns = l.split_whitespace().map(|s| s.parse::<u32>().unwrap());
    println!("{}", if (ns.next().unwrap() * ns.next().unwrap()) % 2 == 0 {
        "Even"
    } else {
        "Odd"
    });
}

Measured memory_bytes: 4352
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int N = 5e4 + 5;

int n,m,q,mod,s,t,r,u[N],v[N],c[N],g,fa[N * 6] , id[N][2][3] , icnt;
bool can[2][1000100];

int get(int x) {
	return fa[x]==x?x:fa[x]=get(fa[x]);
}

void link(int x,int y) {
	x=get(x);
	y=get(y);
	if (x==y) return;
	fa[x]=y;
}

int main() {
	scanf("%d%d%d%d",&n,&m,&q,&mod);
	for (int i = 1;i <= m;i++){
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		g=__gcd(g,abs(c[i]-c[1]));
	}
	if (!g) g=mod;
	mod=__gcd(mod,3*g);
	int z=c[1]%g;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 3; k++)
				id[i][j][k] = ++icnt;

	for (int i = 1;i <= icnt;i++) fa[i]=i;
	for (int i = 1;i <= m;i++){
		int w=(c[i]-z)/g;
		for (int p = 0;p < 2;p++)
		for (int q = 0;q < 3;q++){
			link(id[u[i]][p][q],id[v[i]][1^p][(2*q+w)%3]);
			link(id[v[i]][p][q],id[u[i]][1^p][(2*q+w)%3]);
		}
	}
	
	int mul = z;
	for (int i = 0;i <= (mod << 1);i++){
		can[i & 1][mul] = 1;
		mul = 2 * mul % mod;
	}
	
	while (q--) {
		scanf("%d%d%d",&s,&t,&r);
		int ret=0;
		fo(p,0,1) fo(q,0,2) if (get(id[t][0][0])==get(id[s][p][q])) {
			ret|=can[p][(r+z+(3-q)*g)%mod];
			
			if (ret) break;
		}
		puts(ret?"YES":"NO");
	}
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll n, m;
    cin >> n >> m;
    if(n >= m) cout << 0 << endl;
    else {
        vector<ll> x(m), dif(m-1);
        rep(i, m) cin >> x[i];
        sort(ALL(x));
        rep(i, m-1) dif[i] = x[i+1] - x[i];
        sort(ALL(dif));
        ll ans = 0;
        rep(i, m-n) {
            ans += dif[i];
        }
        cout << ans << endl;
    }
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>

long long gcd(long long a, long long b){
    while(b!=0){
        long long r = a%b;
        a=b;
        b=r;
    }
    return a;
}
 
using namespace std;
int main() {
    long long n, m;
    cin >> n >> m;
    
    vector<int> a(m);
    int ans=0;
    
    for(int i=0;i<m;i++){
        cin >> a[i];
        ans+=a[i];
    }
    
    if(ans > n){
        cout << "-1" << endl;
    }
    else{
        cout << n-ans << endl;
    }
    
    return 0;
}


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

int main(){
  int64_t N;
  cin >> N;
  priority_queue<int64_t,vector<int64_t>,greater<int64_t> > pq;
  pq.push(pow(10,13));
  for(int64_t i=sqrt(N);i>=1;i--){
    if(N%i==0){
      int64_t j=N/i;
      if(i+j-2<pq.top()){
        pq.push(i+j-2);
      }else{
        break;
      }
    }
  }
  cout << pq.top() << endl;
  return 0;
}


Measured memory_bytes: 256