akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++) // ex)REP(i,10) i=0~i=9
#define REPR(i, n) for(int i = n;i >= 0;i--) // ex)REPR(i,10) i=10~i=0
#define FOR(i, m, n) for(int i = m;i < n;i++) //ex)FOR(i,3,10) i=3~i=9
#define FORR(i, m, n) for(int i = m;i >= n;i--) 
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end()); //
#define llong long long //64bitに拡張
#define pb(a) push_back(a)　
#define INF 999999999 //大きな値
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//座標上を探索
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

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

int N,M;
cin >> N >> M;
string ps1[50];
string ps2[50];
bool judge = false;
int judgec = 0;
for(int i=0;i<N;i++){ 
cin >> ps1[i]; 
}
for(int i=0;i<M;i++){ 
cin >> ps2[i]; 
}
for(int j=0;j<N-M+1;j++){
for(int p=0;p<N-M+1;p++){ 
for(int k=0;k<M;k++){
for(int l=0;l<M;l++){ 
if(ps1[j+k][p+l] != ps2[k][l]){ 
judgec = 1;
}
}
}
if(judgec == 0){
judge = true;
break;
} 
judgec = 0;
}
if(judge == true){ 
break;
}	
}

if(judge == true){ cout << "Yes" << endl;}
else{ cout << "No" << endl;}
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int i, j;
  int a, b, c;
  int n, x;

  while (1) {
    int count = 0;
    scanf("%d %d", &n, &x);

    if (n == 0 && x == 0) {
      break;
    } else {
      for (i = n; i >= 3; i--) {
        a = i;
        for (j = a - 1; j >= 2; j--) {
          b = j;
          c = x - a - b;
          if (c > 0 && b > c)
            count++;
        }
      }
    }
    printf("%d\n", count);
  }

  return 0;
}



Measured memory_bytes: 2124
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector<int> h(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}

	--h[0];
	for (int i = 1; i < n; ++i) {
		if (h[i] > h[i - 1]) {
			--h[i];
		}
	}	

	for (int i = 0; i < n - 1; ++i) {
		if (h[i] > h[i + 1]) {
			cout << "No\n";
			return 0;
		}
	}

	cout << "Yes\n";

	return 0;

}

Measured memory_bytes: 640
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s
 
typedef long long ll;
 
using namespace std;

ll modd = 1000*1000*1000+7;

ll binary_search(function<bool(ll)> func, ll start, ll end) {
    /*      func:int ->bool
            returns smallest int x where func(x) evaluates to true, searches in [start,end), it is assumed the values are false, .. , false, true ...
             */
    if (end <= start) {   return end;  }   // has to be here, otherwise func(end-1) in next line could be a problem
    if (!func(end-1)) {  return end;  }
    while (end-start>1) {
        ll mid = (start+end)/2;
        if (func(mid)) {  end = mid;  } else { start = mid;   }
    }
    if (func(start)) {  return start;  } else {  return end;   }
}; 


int main()   {

    ios_base::sync_with_stdio(false);

    cout.precision(17);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
 
//    auto start = chrono::steady_clock::now();
  
//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(n); readint(k);
        int ret = 0;
        forr(i,0,n) {
            readint(kk); ret += (kk>=k);
        }
        cout << ret << endl;

    }
 
//    auto end = chrono::steady_clock::now();
//    cout << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
 
    return 0;
}

Measured memory_bytes: 3620
import time
start = time.time()

import numpy as np
from collections import defaultdict


def get_score(day, contest, prev_list, loss_list, satisfied_matrix):
    plus = satisfied_matrix[day][contest]
    minus = 0
    for type, prev in enumerate(prev_list):
        if type == contest:
            continue
        spend = day - prev
        minus += loss_list[type] * spend

    return plus - minus


def schedule_to_dict(schedule):
    dict = defaultdict(list)
    for day, contest in enumerate(schedule):
        dict[contest].append(day)

    for contest in range(26):
        dict[contest].append(364)

    return dict


def calc_score(schedule, loss_list, satisfied_matrix):
    schedule_dict = schedule_to_dict(schedule)
    plus = 0
    minus = 0
    for contest in range(26):
        day_list = schedule_dict[contest]
        for day in day_list:
            plus += satisfied_matrix[day][contest]

        diff = [0] + day_list[:-1]
        loss_base = loss_list[contest]
        for prev, open in zip(diff, day_list):
            spend = open - prev
            loss = loss_base * spend * (spend+1) // 2
            minus += loss

    return plus - minus


start = time.time()
days = int(input())
loss_list = list(map(int, input().split()))
satisfied_matrix = [list(map(int, input().split())) for _ in range(days)]

ans = np.random.randint(0, 26, 365)
prev = 0
while time.time() - start < 1.8:
    canndidate = np.random.randint(0, 26, 365)
    score = calc_score(canndidate, loss_list, satisfied_matrix)
    if score > prev:
        ans = canndidate


for contest in ans:
    print(contest + 1)

Measured memory_bytes: 27832
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <list>
#include <stdio.h>
#include <tuple>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

int i,j,k,l,m,n;
/////////////////////////////////////////////////////
#define MOD 998244353
#define NMax 303030 
#define tpl tuple<int,int,int>
#define mktp make_tuple

int N;
int p[NMax];
//int bit[20],ex=0;
//vector<tpl> a;

int main(){
    scanf("%d",&N);
   
    for(i=1;i<=N;i++){
        scanf("%d",&p[i]);   
        p[i]=p[i]-i;
        if(p[i]%2){
            printf("No");
            return 0;
        }
    }

    int check[2]={0,0};
    int v1=0;
    for(i=1;i<=N;i++){
        if(check[i&1]!=0&&p[i]==0)break;
        check[i&1]+=p[i];
        if(check[0]*check[1]!=0)break;
        if(p[i]<0){
            if(p[i]+i<v1)break;
            v1=p[i]+i;
        }
        //if(p[i]>0)v1+=2;
        //if(p[i]+v1<0)break;
        if(check[0]+check[1]==0)v1=0;
    }
    if(i!=N+1){
        printf("No");
        //printf("Nob:%d,%d,%d,%d,%d",i,p[i],v1,check[0],check[1]);
        return 0;
    }
    check[0]=0;
    check[1]=0;
    v1=N+1;
    for(i=N;i>=1;i--){
        check[i&1]+=p[i];
        if(check[0]*check[1]!=0)break;
        if(p[i]>0){
            if(p[i]+i>v1)break;
            v1=p[i]+i;
        }
        //if(p[i]<0)v1-=2;
        //if(p[i]+v1>0)break;
        if(check[0]+check[1]==0)v1=N+1;
    }
    if(i!=0){
        printf("No");
        return 0;
    }
    printf("Yes");
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
    string S;
    cin>>S;
    ll ans = 1;
    bool flag =false;
    rep(i,1,S.size()){
        if(S[i] == S[i-1] && flag == false){
            i++;
            if(i < S.size())ans++;
            flag =true;
        }
        else{
            flag = false;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <array>
#include <queue>

using namespace std;

int main()
{
    double t, x;
    cin >> t >> x;
    double ans = t / x;
    printf("%.8f", ans);
    return 0;
}


Measured memory_bytes: 888
W, H, N = list(map(int, input().split()))
x_low, x_up = 0, W
y_low, y_up = 0, H
for _ in range(N):
    x, y, a = list(map(int, input().split()))
    if a == 1:
        x_low = max(x_low, x)
    elif a == 2:
        x_up = min(x_up, x)
    elif a == 3:
        y_low = max(y_low, y)
    else:
        y_up = min(y_up, y)
print(max(0, x_up - x_low) * max(0, y_up - y_low))


Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
int N, W, w, v, ans;
unordered_map<int, int> H;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	H[0] = 0;
	cin >> N >> W;
	for (int i = 0 ; i < N ; ++i) {
		cin >> w >> v;
		vector<pair<int, int>> tmp;
		for (const auto &p : H) {
			tmp.push_back(p);
		}
		for (const auto &p : tmp) {
			int nv = p.first + v;
			int nw = p.second + w;
			if (nw <= W) {
				auto it = H.find(nv);
				if (it == H.end()) {
					H[nv] = nw;
				} else {
					it->second = min(it->second, nw);
				}
				ans = max(ans, nv);
			}
		}
	}
	cout << ans << '\n';
}

Measured memory_bytes: 3212
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int H = 1e5 + 10;
const int N = 1e3 + 10;
ll h, n;
ll A[N], B[N];
ll dp[N][H];
int main(){
    cin >> h >> n;

    for(int i = 1; i <= n; i ++)
    {
        cin >> A[i] >> B[i];
    }
        for(int j = 0; j <= h; j ++)
    {
        if(j % A[1] == 0) dp[1][j] = (j / A[1]) * B[1];
        else dp[1][j] = ((j / A[1]) + 1) * B[1];
        //cout << 1 <<" "<< j<<" " << dp[1][j] << endl;
    }
    for(int i = 2; i <= n; i ++)
    {
        for(int j = 0; j <= h; j ++)
        {
            dp[i][j] = dp[i-1][j];
            if(j < A[i]) dp[i][j] = min(dp[i][j], B[i]);
            if(j >= A[i]) dp[i][j] = min(dp[i][j - A[i]] + B[i], dp[i][j]);
            //cout << i <<" " << j << " " << dp[i][j] << endl;
        }
    }
    cout << dp[n][h] << endl;
    return 0;
}


Measured memory_bytes: 780672
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

const ll p = 1e7+7;;
ll acc[300001];
ll pp[300001];

int main() {
  int n, m;
  while(cin>>n>>m) {
    string s;
    cin >> s;
    acc[0] = 0;
    pp[0] = 1;
    REP(i,s.size()) {
      acc[i+1] = acc[i]*p + s[i];
      pp[i+1] = pp[i] * p;
    }
    int left = 0;
    int right = 0;
    set<ll> se;
    REP(i,m) {
      string t;
      cin >> t;
      if (t=="R++") {
        right++;
      } else if (t=="R--") {
        right--;
      } else if (t=="L++") {
        left++;
      } else {
        left--;
      }
      ll hash = acc[right+1]-acc[left]*pp[right-left+1];
      // cout << left << " " << right << " " << hash << endl;
      // cout << acc[right+1] << " "<< acc[left] << " " << pp[right-left] << endl;
      se.insert(hash);
    }
    cout << se.size() << endl;
  }
}

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

const int N = 1e6 + 100;

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int X, Y;
    cin >> X >> Y;
    for(int a = 0; a <= X; a++) {
        int b = X-a;
        if(2*a + 4*b == Y) {
            cout << "Yes" << endl;
            exit(0);
        }
    }
    cout << "No";

    return 0;
}



Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	ll n, k; cin >> n >> k;
	ll out = k;
	rep(i, n - 1) {
		out *= k - (ll)1;
	}
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int a = input.nextInt();
		int[] num = new int[a];
		long sum = 0;
		int temp;
		for(int i = 0; i < a; i++) {
			num[i] = input.nextInt();
		}
		for(int j = 0; j < num.length; j++) {
			sum += num[j];
		}
		for (int i = 0; i < num.length; i++) {
			int min = num[i];
            temp = i;
			for (int j = i + 1; j < num.length; j++) {
				if (min > num[j]) {
					min = num[j];
					temp = j;
				}
			}
			num[temp] = num[i];
			num[i] = min;
		}
		System.out.println(num[0]+" "+num[a-1]+" "+sum);
	}
}


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

using namespace std;

const int N = 200010;

int n, x;
int a[N];
long long sum[N];

int main() {
	scanf("%d %d", &n, &x);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		sum[i] = sum[i - 1] + a[i];
	}
	long long res = (1ll << 60);
	for (int i = 1; i <= n; i++) {
		int r = n;
		int cnt = 0;
		long long foo = 0ll;
		bool isBreak = 0;
		while (r > 0) {
			int l = max(0, r - i);
			cnt++;
			if (cnt == 1) {
				foo += 5ll * (sum[r] - sum[l]);
			} else {
				foo += (2ll * cnt + 1ll) * (sum[r] - sum[l]);
			}
			if (foo > res) {
				isBreak = 1;
				break;
			}
			r = l;
		}
		if (isBreak) {
			continue;
		}
		foo += 1ll * i * x;
		// cout << i << " " << foo << endl;
		res = min(res, foo);
	}
	cout << res + 1ll * n * x << endl;
	return 0;
}

Measured memory_bytes: 2560
from heapq import heappush, heappop, heapify

n = int(input())
values = list(map(int, input().split()))

heapify(values)

while len(values) > 1:
  a = heappop(values)
  b = heappop(values)
  heappush(values, (a+b) / 2)
  
print(values[0])


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

int last(vector<int> &ts, int d, int i) {
  for (int idx = d; idx >= 0; idx--) {
    if (ts[idx] == i) {
      return idx + 1;
    }
  }
  return 0;
}

int main(void) {
  int d;
  cin >> d;
  vector<int> cs(26);
  for (int &c : cs) cin >> c;
  vector<vector<int>> sss(d, vector<int>(26));
  for (vector<int> &ss : sss) {
    for (int &s : ss) cin >> s;
  }
  vector<int> ts(d);
  for (int &t : ts) cin >> t;

  vector<int> satisfy(d);
  for (int i = 0; i < d; i++) {
    satisfy[i] = i == 0 ? 0 : satisfy[i - 1];
    satisfy[i] += sss[i][ts[i] - 1];
    for (int j = 0; j < 26; j++) {
      satisfy[i] -= cs[j] * ((i + 1) - last(ts, i, j + 1));
    }

    cout << satisfy[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
const ll MOD = 1e9+7;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
#define fs first
#define sc second


const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
template<typename T>
T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T>
T ngcd(vector<T> a){
    T res;
    res = a[0];
    for(int i = 1; i < a.size() && res != 1; i++) {
        res = gcd(a[i], res);
    }
    return res;
}
 
template<typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
T nlcm(vector<T> numbers) {
    T res;
    res = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        res = lcm(res, numbers[i]);
    }
    return res;
}

// 割り算の切り上げ処理
template<typename T>
T round_up(T a, T b) {
  return (a + b - 1) / b;
}

// 約数列挙
template<typename T>
vector<T> calc_divisor(T n) {
   vector<T> res;
   for (T i = 1LL; i*i <= n; ++i) {
       if (n % i == 0) {
           res.push_back(i);
           T j = n / i;
           if (j != i) res.push_back(j);
       }
   }
   sort(res.begin(), res.end());
   return res;
}

// 素数判定
template<typename T>
bool isPrime(T x){
    T i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;


int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int a,b,c;
    cin >> a >> b >> c;
    print(a * b / 2);
    
}


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

int main() {
  int n;
  cin >> n;
  bool flag = false;
  for(int i=0; i<3; i++) {
    if(n%10 == 7) flag = true;
    n /= 10;
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
string str;
int main()
{
	cin>>str;
	for(int i=0;i<3;i++)
		if(str[i]==str[i+1])
		{
			printf("Bad");
			return 0;
		}
	printf("Good");
	return 0;
}

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

vector<vector<int>> g;
vector<int> id;
vector<ll> sum;

int f(int x, int ida){
	id.at(x) = ida;
	rep(i, g.at(x).size()){
		if(id.at(g.at(x).at(i)) != ida) f(g.at(x).at(i), ida);
	}
	return 0;
}

int main(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> ce(m, vector<int>(2));
	rep(i, m) cin >> ce.at(i).at(0) >> ce.at(i).at(1);
	g = vector<vector<int>>(n, vector<int>(0));
	id = vector<int>(n);
	sum = vector<ll>(n);
	vector<ll> a(m);
	ll ans = (ll)n*((ll)n-1)/2;
	rep(i, n){
		id.at(i) = i;
		sum.at(i) = 1;
	}
	for(int i=m-1; i>0; i--){
		int c0 = ce.at(i).at(0) -1;
		int c1 = ce.at(i).at(1) -1;
		a.at(i) = ans;
		if(id.at(c0) != id.at(c1)){
			ans -= sum.at(id.at(c0)) * sum.at(id.at(c1));
			if(sum.at(id.at(c0)) < sum.at(id.at(c1))){
				sum.at(id.at(c1)) = sum.at(id.at(c0)) + sum.at(id.at(c1));
				f(c0, id.at(c1));
			}else{
				sum.at(id.at(c0)) = sum.at(id.at(c0)) + sum.at(id.at(c1));
				f(c1, id.at(c0));
			}
			g.at(c0).push_back(c1);
			g.at(c1).push_back(c0);
		}
	}
	a.at(0) = ans;
	rep(i, m) cout << a.at(i) << endl;
	return 0;
}

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

int main()
{
  int N;
  cin >> N;
  
  int A[N],B[N-1];
  int C[N],D[N];	//C[i]はiにいる残りモンスター,D[i]は勇者が倒せる残りモンスター数
  
  long long ans=0;
  for(int i=0;i<=N;i++){
    cin >> A[i];
  }
  for(int i=0;i<N;i++){
    cin >> B[i];
  }
  
  for(int i=0;i<N;i++){
	/*
    if(b[i]<a[i])
			ans+=b[i];
	else
	{
			b[i]-=a[i];
			ans+=a[i];
			a[i]=0;
			if(b[i]<a[i+1])
			{
				ans+=b[i];
				a[i+1]-=b[i];
			}
			else
			{
				ans+=a[i+1];
				a[i+1]=0;
			}
	}
    */
    if(A[i]>B[i]){
      ans+=B[i];	//iの勇者はiのモンスターを倒せるだけ倒して終わり
    }
    else{
      ans+=A[i];	//A[i]のモンスターを全て討伐する
      D[i]=B[i]-A[i];	//勇者が倒せる残りモンスター
      A[i]=0;
      
      if(A[i+1]>D[i]){
        ans+=D[i];	//iの勇者はi+1のモンスターを倒せるだけ倒して終わり
        A[i+1]= A[i+1]-D[i];
      }
      else{
        ans+=A[i+1];	//iの勇者はA[i+1]のモンスターを全て討伐する
        A[i+1]=0;
      }
    }
    
  }
  
  cout << ans;
  
  return 0;
  
}



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

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    mint choose(int n, int a){
        mint x = 1 ,y = 1;
        for(int i=0; i<a; ++i){
            x *= n-i;
            y *= i+1;
        }
        return x / y;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    mint ans=mint(2).pow(n);
    ans=ans-1-mint().choose(n,a)-mint().choose(n,b);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3648
n=int(input())
a=input().split()
a=list(map(int,a))
mean=sum(a)/n
for i in range(n):
    a[i]=abs(a[i]-mean)
k=a[0]
j=0
for i in range(n):
    if  a[i]<k:
        k=a[i]
        j=i
print(j)

Measured memory_bytes: 3060
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
CN = 0

for i in range(N-1):
    if A[i+1] - A[i] == 1:
        CN += C[A[i]-1]

print(sum(B)+CN)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	string s; cin>>s;
	int ans = -1;
	for(int i=0; i<s.size(); i++){
		for(int j=0; j<s.size()+1; j++){
			int cnt = 0;
			string aux = s.substr(i, j);
			//cout<<aux<<endl;
			for(int k=0; k<aux.size(); k++){
				if(aux[k]=='A'||aux[k]=='C'||aux[k]=='G'||aux[k]=='T')
					cnt++;
				else break;
			}
			if(cnt==aux.size())
				ans = max(ans, cnt);
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3604
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 12 00:21:05 2020

@author: liang
"""

N = int(input())
A = [int(x) for x in input().split()]

A.sort()
A += [-1]
dp = [0] + [True]*10**6
def Solve():
    if A[0] == 1:
        if len(A) >= 2 and A[1] == 1:
            return 0
        else:
            return 1
    k = 0
    for i in range(1,10**6+1):
        if i == A[k]:
            #print("A",i)
            #kの処理
            tmp = A[k]
            cnt = 0
            while k <= N-1 and A[k] == tmp:
                #print("B",k,tmp)
                cnt += 1
                if cnt == 2:
                    dp[tmp] = False
                k += 1
            #倍数の消去
            for j in range(2*i,10**6+1,i):
                #print("C")
                dp[j] = False
    ans = 0
    for a in A[:-1]:
        if dp[a]:
            ans += 1
    return ans

ans = Solve()
print(ans)

Measured memory_bytes: 105292
#include<bits/stdc++.h>
#define register rg
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
typedef long long ll;
int main() {
	//file("a");
	int  A,B,C;
	cin>>A>>B>>C;
	if(A+B>=C)
		cout<<B+C,exit(0);
	else
		cout<<B+A+B+1;
	return 0;
}


Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    M, *DC = map(int, read().split())
    total = sum(d * c for d, c in zip(DC[::2], DC[1::2]))
    ans = sum(DC[1::2]) - 1 + (total - 1) // 9
    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 28240
#include<iostream>

using namespace std;

struct P
{
	int x,y;
};

P maxP(const P a,const P b){
	int la=a.x*a.x+a.y*a.y;
	int lb=b.x*b.x+b.y*b.y;

	if(la>lb)return a;
	if(la<lb)return b;

	if(a.x>b.x)
		return a;
	else
		return b;
}

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		P d,p={0,0},m={0,0};
		while(cin >> d.x >> d.y, d.x|d.y){
			p.x+=d.x;p.y+=d.y;
			m=maxP(m,p);
		}
		cout << m.x << " " << m.y << endl;
	}

	return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

void solve() {
    LL a, b, c, d;
    cin >> a >> b >> c >> d;
    LL ans = a * c;
    ans = max(ans, a * d);
    ans = max(ans, b * c);
    ans = max(ans, b * d);
    cout << ans << '\n';
}

int main() {
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    // cerr << fixed << setprecision(10);
    // cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << '\n';
    return 0;
} 

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(c) begin(c), end(c)
#define ok() puts(ok?"Yes":"No");
template<class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int N;
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};

istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
int main() {
  cin >> N;
  vll A(N);
  rep(i,N)cin >> A[i];
  vll SA(N+1);
  rep(i,N) (SA[i+1] += SA[i] + A[i]) %= mod;
  mint ans = 0;
  rep(i,N) {
    (ans += ((ll) A[i] * (SA[N]-SA[i+1])));
  }
  cout << ans.x << endl;
  // vector<mint> SA(N+1);
  // rep(i,N) SA[i+1] += SA[i] + A[i];
  // mint ans = 0;
  // for (ll i=0; i<N;i++) {
  //   ans += (i+1) * (SA[N] - SA[i+1]).x;
  //   cout << (i+1) * (SA[N] - SA[i+1]).x << endl;
  // }
  // cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 6356
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    long long solve(vector<int>& A) {
        int n = A.size();

        auto build = [&](vector<int>& A) {
            int n = A.size();
            int h = 0;
            while (1 << (h + 1) <= n) {
                ++h;
            }

            vector<vector<int>> res(n, vector<int>(h + 1, 0));
            for (int i = 0; i < n; ++i) {
                res[i][0] = A[i];
            }
            for (int j = 1; j <= h; ++j) {
                for (int i = 0; i < n; ++i) {
                    int k = i + (1 << (j - 1));
                    res[i][j] = res[i][j - 1];
                    if (k < n) {
                        res[i][j] = max(res[i][j], res[k][j - 1]);
                    }
                }
            }
            return res;
        };

        auto find = [&](vector<vector<int>>& maxs, int beg, int x) {
            int h = maxs[0].size();
            int n = maxs.size();
            int res = beg;
            for (int i = h - 1; i >= 0 && res < n; --i) {
                if (res + (1 << i) > n) {
                    continue;
                }
                if (maxs[res][i] <= x) {
                    res += 1 << i;
                }
            }
            return res;
        };

        reverse(A.begin(), A.end());
        auto maxsL = build(A);
        reverse(A.begin(), A.end());
        auto maxsR = build(A);

        long long res = 0;
        for (int i = 0; i < n; ++i) {
            int x = A[i];

            int l = find(maxsL, n - 1 - i, x);
            int ll = find(maxsL, l + 1, x);

            l = n - 1 - l;
            ll = n - 1 - ll;
            ll = max(-1, ll);

            int r = find(maxsR, i, x);
            int rr = find(maxsR, r + 1, x);
            rr = min(n, rr);

            if (l >= 0 || r < n) {
                long long cnt = (l - ll) * 1LL * (r - i) + (i - l) * 1LL * (rr - r);
                res += cnt * x;
            }
        }
        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    Solution sol;
    cout << sol.solve(A) << "\n";

    return 0;
}

Measured memory_bytes: 20992
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		int cnt = 0, ocnt = 0;
		int[] a = new int[3];
		while (ocnt < 3) {
			String s = in.next();
			if ("HIT".equals(s)) {
				if (a[2] == 1) cnt++;
				a[2] = a[1];
				a[1] = a[0];
				a[0] = 1;
			} else if ("HOMERUN".equals(s)) {
				int t = 0;
				for (int i=0; i<3; i++) {
					t += a[i];
				}
				cnt += t + 1;
				a = new int[3];
			} else {
				ocnt++;
			}
		}
		out.println(cnt);
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		int n = in.nextInt();
		while(n-- > 0) solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

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

using namespace std;

#define ll long long int
#define get(a) ll a; cin >> a;
#define show(a) cout << a << endl;
#define full(p) p.begin(), p.end()
#define sz(a) (ll)(a.size())
#define pb push_back


bool is_good(int n, bool arr[])
{
	// check if all numbers are admissible or not
	while(n)
	{
		int temp = n%10;
		n /= 10;
		if(arr[temp] == false)
			return false;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout<<fixed;
	////////////////////////////////
	get(n);
	get(k);
	bool arr[10] = {true};
	for (int i = 0; i < 10; ++i)
	{
		arr[i] = true;
	}
	for (int i = 0; i < k; ++i)
		{
			get(ki);
			arr[ki] = false;
		}

	for(int i = n; ; i++)
	{
		if(is_good(i, arr))
		{
			cout << i << endl;
			break;
		}

	}
	return 0;
}

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

int main(){
  vector<vector<int>> A(3,vector<int>(3));
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cin >> A.at(i).at(j);
    }
  }
  
  int N;
  cin >> N;
  
  for(int k = 0; k < N; k++){
    int b;
    cin >> b;
    
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        if(A.at(i).at(j) == b){
          A.at(i).at(j) = -1;
        }
      }
    }
  }
/*  
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cout << A.at(i).at(j) << " ";
    }
    cout << endl;
  }
  cout << endl;
*/  
  string ans = "No";
  
  if(A.at(0).at(0) < 0){
    if(A.at(0).at(1) < 0){
      if(A.at(0).at(2) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  
  if(A.at(0).at(0) < 0){
    if(A.at(1).at(0) < 0){
      if(A.at(2).at(0) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  
  if(A.at(0).at(0) < 0){
    if(A.at(1).at(1) < 0){
      if(A.at(2).at(2) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  
  if(A.at(1).at(0) < 0){
    if(A.at(1).at(1) < 0){
      if(A.at(1).at(2) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  if(A.at(0).at(1) < 0){
    if(A.at(1).at(1) < 0){
      if(A.at(2).at(1) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  if(A.at(0).at(2) < 0){
    if(A.at(1).at(2) < 0){
      if(A.at(2).at(2) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
    if(A.at(1).at(1) < 0){
      if(A.at(2).at(0) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  if(A.at(2).at(0) < 0){
    if(A.at(2).at(1) < 0){
      if(A.at(2).at(2) < 0){
        ans = "Yes";
        //cout << "Yes" << endl;
      }
    }
  }
  
  cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

string w[114514];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll x[1333], y[1333];
	cin>>n;
	bool odd=false, even=false;
	ll ma=-1;
	REP(i, n){
		cin>>x[i]>>y[i];
		if(abs(x[i])+abs(y[i])&1){
			odd=true;
		}
		else{
			even=true;
		}
	}
	if(odd && even){
		cout<<-1<<'\n';
		return 0;
	}
	int m=31, d[40];
	if(even){
		cout<<32<<'\n';
		cout<<1<<' ';
		REP(i, n){
			w[i]="R";
			--x[i];
		}
	}
	else{
		cout<<31<<'\n';
	}
	REP(i, m){
		d[i]=1<<i;
	}
	REP(i, n){
		FORR(j, 0, m){
			if(x[i]+y[i]<0 && x[i]-y[i]<0){
				w[i]+="L";
				x[i]+=d[j];
			}
			else if(x[i]+y[i]>0 && x[i]-y[i]>0){
				w[i]+="R";
				x[i]-=d[j];
			}
			else if(x[i]+y[i]<0 && x[i]-y[i]>0){
				w[i]+="D";
				y[i]+=d[j];
			}
			else{
				w[i]+="U";
				y[i]-=d[j];
			}
		}
	}
	FORR(i, 0, m){
		cout<<d[i]<<" \n"[i==m-1];
	}
	REP(i, n){
		cout<<w[i]<<'\n';
	}
	return 0;
}


Measured memory_bytes: 1280
// 2014/12/10 Tazoe

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int p1, p2, p3, j1, j2;
	cin >> p1;
	cin >> p2;
	cin >> p3;
	cin >> j1;
	cin >> j2;

	int p = min(min(p1, p2), p3);
	int j = min(j1, j2);

	cout << p+j-50 << endl;

	return 0;
}

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

int main()
{
    string S, T, U;
    int A, B;
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    if(U==S) A--;
    else if(U==T) B--;

    cout << A << " " << B << endl;
    
    return 0;
}


Measured memory_bytes: 256
#ifndef HOME
#pragma GCC optimize "-O3"
#endif

#include <bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using namespace std;

ll X;

struct E {
    ll b, l, u;

    ll fpr() const {
        return u * X - u * b + l * b;
    }
};


bool operator<(E a, E b) {
    return a.fpr() > b.fpr();
}

const int MX = 100 * 1000 + 7;

ll prof[MX];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n >> X;

    vector<E> e(n);
    for (E& x : e) {
        cin >> x.b >> x.l >> x.u;
    }

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

    ll score = 0;
    for (int i = n - 1; i >= 0; i--) {
        score -= e[i].l * e[i].b;
    }

    for (int i = 0; i < n; i++) {
        prof[i] = e[i].fpr();
        if (i) {
            prof[i] += prof[i - 1];
        }
    }

    ll lg = -1, rg = n * X;
    while (rg - lg > 1) {
        ll mg = (lg + rg) >> 1;
        int full = mg / X, more = mg % X;
        bool ok = false;
        for (int i = 0; i < n; i++) {
            ll cp = 0;
            if (full > 0) {
                cp = prof[full - 1];
                if (i < full) {
                    cp -= e[i].fpr();
                    cp += e[full].fpr();
                }
            }
            cp += 1ll * e[i].l * e[i].b;
            ll delta = more - e[i].b;
            ll cf = (delta > 0) ? e[i].u : e[i].l;
            cp += delta * cf;
            if (cp + score >= 0) {
                ok = true;
            }
        }
        if (ok) {
            rg = mg;
        } else {
            lg = mg;
        }
    }
    cout << rg << "\n";
    return 0;
}



Measured memory_bytes: 3328
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}



int main(){
  
  string s,t;cin>>s>>t;
  cout << t << s << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;
using Graph=vector<string>;
int h,w;
Graph field;
vector<vector<int>> cnt;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
vector<vector<bool>> seen;
queue<pair<int,int>> que; 
void bfs(int x=0,int y=0,int c=1){
  cnt[x][y]=c;
  seen[x][y]=true;
  for (int i = 0; i < 4; ++i)
  {
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0 || ny<0 || nx>=h || ny>=w) continue;
    if(seen[nx][ny]) continue;
    if(field[nx][ny]=='#') continue;
    que.push(make_pair(nx,ny));
    seen[nx][ny]=true;
  }
}

int main()
{
  cin>>h>>w;
  field.resize(h);
  for (int i = 0; i < h; ++i)
  {
    cin>>field[i];
  }
  
  cnt.resize(h);
  seen.resize(h);
  for (int i = 0; i < h; ++i)
  {
    cnt[i]=vector<int>(w,-1);
    seen[i]=vector<bool>(w,false);
  }

  bfs();

  while(!que.empty()){
    int a=que.front().first,b=que.front().second;
    que.pop();
    int c=1000;
    for (int i = 0; i < 4; ++i)
    {
      int x=a+dx[i],y=b+dy[i];
      if(x<0 || y<0 || x>=h || y>=w) continue;
      if(cnt[a+dx[i]][b+dy[i]]==-1) continue;
      c=min(cnt[a+dx[i]][b+dy[i]],c);
    }
    bfs(a,b,c+1);
  }
  
  int ans=0;
  for (int i = 0; i < h; ++i)
  {
    for (int j = 0; j < w; ++j)
    {
      if(field[i][j]=='.') ans++;
    }
  }
  if(cnt[h-1][w-1]==-1) {
    cout<<-1;
    return 0;
  }
  cout<<ans-cnt[h-1][w-1];
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long a, b, x;
    cin >> a >> b >> x;
    if (a != 0) {
        cout << ((b / x) + 1) - (((a - 1) / x) + 1) << endl;
    }
    else {
        cout << (b / x) + 1 << endl;
   }}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
#include <iomanip>
#include <cmath>

using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s[0] != s[1] && s[2] == s[3] && s[4] == s[5])
        cout<<"Yes";
    else
        cout<<"No";




    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/10/31  Problem: ketadp2 / Link: http://tdpc.contest.atcoder.jp/tasks/tdpc_number  ----- */
/* ------問題------

N 以下の正整数であって、十進法表記したときの各桁の数の和が D の倍数であるものの個数を mod 1,000,000,007 で求めよ。

-----問題ここまで----- */
/* -----解説等-----

dp[今i番目の数を見ている][mod D][target未満が確定しているか？->1]:=総数
として桁DP

----解説ここまで---- */


LL ans = 0LL;
LL dp[10004][102][2];
int D;
LL f(string &target, int i, int d = 0, int less = 0) {
	if (i == -1) {
		if (d%D == 0)return 1;
		else return 0;
	}

	if (dp[i][d][less] != -1 && less == 1)return dp[i][d][less];
	LL res = 0;
	int num = target[i] - '0';
	int Max = less ? 9 : num;
	FOR(nx, 0, Max + 1) {
		res += f(target, i - 1, (d + nx) % D, less || (nx<Max)) % MOD;
	}
	if (less == 1)
		return  (dp[i][d][less] = (res%MOD));
	return res;
}


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

	string N;
	cin >> N>>D;
	fill(**dp, **dp + 10004 * 102 * 2, -1);
	reverse(ALL(N));
	ans = f(N, SZ(N) - 1);
	ans--;
	//debug(ans);

	cout << (ans + MOD) % MOD << "\n";

	return 0;
}


Measured memory_bytes: 17152
#include <bits/stdc++.h>
using namespace std;
int main(void){
   int N;
   cin >> N;
   vector<int> A(N),B(N-1);
   for(int i = 0; i < N-1; i++){
       cin >> B[i];
   }
   A[0] = B[0];
   A[N-1] = B[N-2];
   int S = A[0] + A[N-1];
   for(int i = 1; i < N - 1; i++){
       A[i] = min(B[i],B[i-1]);
       S += A[i];
   }
   cout << S << endl;
}


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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

void hawawa()
{
	int n, m;
	cin >> n >> m;
	Vec<string> a(n), b(m);
	for (auto&& i : a) {
		cin >> i;
	}
	for (auto&& i : b) {
		cin >> i;
	}
	for (int i = 0; i + m <= n; i++) {
		for (int j = 0; j + m <= n; j++) {
			if (a[i].substr(j, m) == b[0]) {
				for (int k = 1; k < m; k++) {
					if (a[i + k].substr(j, m) != b[k]) {
						goto end;
					}
				}
				cout << "Yes\n";
				return;
			}
		end:;
		}
	}
	cout << "No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	hawawa();
}


Measured memory_bytes: 256