akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int INF = numeric_limits<int>::max();

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    string s; cin >> s;
    if (stoi(s.substr(0,4)) <= 2019 && stoi(s.substr(5,2)) <= 4)
        cout << "Heisei" << endl;
    else
        cout << "TBD" << endl;
    return 0;
}


Measured memory_bytes: 256
// F - Intervals on Tree
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin>>n;
	int64_t E = 0, V = 1LL*n*(n+1)*(n+2)/6;
	for(int i=0; i<n-1; ++i){
		int u, v; cin>>u>>v;
		if(u > v) swap(u, v);
		E += 1LL*u*(n-v+1);
	}
	cout<< V-E <<endl;
}


Measured memory_bytes: 3640
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<bitset>
typedef long long ll;
#define pi 3.1415926535897931159979635

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int b,c;
    cin>>b;
    cout<<b+b*b+b*b*b<<"\n";
    

    return 0;
}

Measured memory_bytes: 3580
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  int i;
  int N;
  scanf("%d", &N);
  int A[100010];
  int ans = 0;
  for (i = 1; i < N+1; i++) {
    scanf("%d", &A[i]);
  }
  A[0] = 0;
  A[N+1] = 0;
  int kotae[100010];
  for (i = 1; i < N+2; i++) {
    ans += abs(A[i] - A[i-1]);
  }
  for (i = 1; i <= N; i++) {
    if ((A[i] - A[i-1]) * (A[i+1] - A[i]) >= 0) {
      kotae[i] = ans;
    } else if (A[i] > A[i-1]) {
      kotae[i] = ans - (A[i] - max(A[i-1], A[i+1]))*2;
    } else {
      kotae[i] = ans - (min(A[i-1], A[i+1]) - A[i])*2;
    }
  }
  for (i = 1; i <= N; i++) {
    printf("%d\n", kotae[i]);
  }
  return 0;
}


Measured memory_bytes: 1920
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        
        String S = sc.next();
        
        int ans = 0;
        for(int i = 0; i < 4; i++){
            if( S.charAt(i) == '+' ) ans++;
            if( S.charAt(i) == '-' ) ans--;
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 22740
import std.conv, std.stdio;
import std.algorithm, std.array, std.range, std.string;
void main()
{
    auto buf = readln.chomp.split.to!(ulong[]);
    buf[0].solve(buf[1]).writeln;
}

ulong solve(in ulong a, in ulong b)
{
    assert (a <= b);
    if (a == b)
        return a;
    if (a.even && b.odd)
        return (~(b-a)>>1) & 1;
    if (a.odd)
        return a ^ solve(a + 1, b);
    if (b.even)
        return solve(a, b - 1) ^ b;
    assert (false);
}

bool even(in ulong a)
{
    return !(a & 1);
}
bool odd(in ulong a)
{
    return a & 1;
}


Measured memory_bytes: 256
/* 
**
**   author:  Blue Fire
**   created:  19/09/2020
**
*/
 
#include <iostream>
#include <iomanip>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <chrono>
#include <cmath>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <unistd.h>
#include <queue>
#include <list>
#include <random>
#include <bitset>
#include <fstream>
#include <limits>
using namespace std;
typedef long long llong;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	cout << s << ((s[s.length()-1] == 's')? "es" : "s");
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
/*----------------------------Template-Begins----------------------------*/
typedef vector<int> VI;
typedef long long int ll;
typedef pair<int,int> PII;
typedef double db;
#define fastIO() ios_base::sync_with_stdio(0);cin.tie(nullptr)
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define DOTEST(t) int t;cin>>t; while(t--)
#define TEST cout<<"-------Executed--------\n";
#define all(x) x.begin(),x.end()
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
ll binexp(ll a,ll b){ll ans=1;while(b>0){if(b&1)ans = ans*a;a = a*a;b /=2;}return ans;}
ll modexp(ll a,ll b,ll m){ll ans=1;while(b>0){if(b&1){ans = ans*a%m;}a = a*a%m; b/=2;}return ans%m;}
/*---------------------------Template-Ends------------------------------ */
ll countbits(ll n){
    int c = 0;
    while(n){
        c++;
        n = n>>1;
    }
    return  c;
}
/*--------------------------------Main-----------------------------------*/
int main(){
    fastIO();
    int n;
  cin>>n;
  int x = n/1000;
  if(n%1000==0)cout<<"0";
  else cout<<((x+1)*1000-n);
}
/*-----------------------------------------------------------------------*/


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define All(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main() {
  Cin(int, n, d);
  int cnt = 1;
  while (true) {
    n -= 2 * d + 1;
    if (n <= 0) break;
    cnt++;
  }
  cout << cnt << endl;
}

int main() {
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i=0;i<n;i++) a[i] = sc.nextLong();
		sc.close();
		long count1 = 0;
		long sum = 0;
		//System.out.println("-----------------------");
		for(int i=0;i<n;i++){
			sum += a[i];
			//System.out.print(sum+" -> ");
			if(i%2==0&&sum<=0){
				count1 += 1-sum;
				sum = 1;
			} else if(i%2==1&&sum>=0){
				count1 += sum+1;
				sum = -1;
			}
			//System.out.println(sum+" "+count1);
		}
		//System.out.println("-----------------------");
		sum = 0;
		long count2 = 0;
		for(int i=0;i<n;i++){
			sum += a[i];
			//System.out.print(sum+" -> ");
			if(i%2==1&&sum<=0){
				count2 += 1-sum;
				sum = 1;
			} else if(i%2==0&&sum>=0){
				count2 += sum+1;
				sum = -1;
			}
			//System.out.println(sum+" "+count2);
		}
		//System.out.println("-----------------------");
		System.out.println(Math.min(count1, count2));

	}

}


Measured memory_bytes: 64484
k = input()
z = k.count('0')
o = k.count('1')

if len(k) == 1:
    print(0)
else:
    if z == 0 or o == 0:
        print (0)
    else:
        if z < o:
            print(z*2)
        else:
            print(o*2)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const ll INF = 1LL << 30;
int N, W;
int w[110], v[110];
ll minw = INF;
vector<int> v2[4];

ll dfs(int idx, ll rem) {
  if (idx == 4) return 0;
  ll res = dfs(idx + 1, rem);
  ll sum = 0;
  for (int i = 0; i < v2[idx].size(); i++) {
    sum += v2[idx][i];
    if (rem - (i + 1) * (minw + idx) < 0) break;
    res = max(res, dfs(idx + 1, rem - (i + 1) * (minw + idx)) + sum);
  }
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> W;
  for (int i = 0; i < N; i++) {
    cin >> w[i] >> v[i];
    minw = min(minw, (ll)w[i]);
  }
  for (int i = 0; i < N; i++) {
    v2[w[i] - minw].emplace_back(v[i]);
  }
  for (int i = 0; i < 4; i++) {
    sort(v2[i].rbegin(), v2[i].rend());
  }
  cout << dfs(0, W) << endl;

  return 0;
}

Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}
//20:36

fn main(){
    let line: Vec<usize> = read_as_vec();
    let (a, b, c, x, y) = (line[0], line[1], line[2], line[3], line[4]);

    if a + b < 2*c{
        println!("{}", a*x+b*y);
        return;
    }

    let mut ans = 2*c * cmp::min(x, y);
    if y == x{
        println!("{}", ans);
        return;
    }

    let (a, x) = if x < y {
        (b, y-x)
    }else{
        (a, x-y)
    };

    if a*x < 2*c*x{
        ans += a*x;
    }else{
        ans += 2*c*x;
    }

    println!("{}", ans);
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

typedef complex<double> P;
typedef vector<P> Polygon;

double dot(P const& a, P const& b) {
  return real(conj(a)*b);
}
double cross(P const& a, P const& b) {
  return imag(conj(a)*b);
}


#define prev(G, i) ( G[(i-1 + G.size()) % G.size()] )
#define curr(G, i) ( G[i] )
#define next(G, i) ( G[(i+1) % G.size()] )

// contain: 2, on segment: 1, the other case: 0
int contains(Polygon const& G, P const& p) {
  bool x = false;
  for(int i=0; i<(int)G.size(); i++) {
    P v1 = curr(G, i)-p, v2 = next(G, i) - p;
    if( v1.imag() > v2.imag() ) swap(v1, v2);
    if( v1.imag() <= 0 && 0 < v2.imag() && cross(v1, v2) > 0 ) x = !x;
    if( cross(v1, v2) == 0 && dot(v1, v2) <= 0 ) return 1;
  }
  return (x?2:0);
}

int main() {
  
  int N; cin >> N;
  Polygon G;
  rep(i, N) {
    double x, y; cin >> x >> y;
    G.push_back(P(x, y));
  }
  int Q; cin >> Q;
  rep(i, Q) {
    P p; cin >> p.real() >> p.imag();
    cout << contains(G, p) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define vi vector<int>
#define vvi vector<vector<int> >
#define rep(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define mem(a,b) memset(a , b , sizeof a );

int main()
{
	string s,t;
	cin>>s>>t;
	ll n=s.length();
	ll m=t.length();
	ll dp[n+1][m+1];
	rep(i,0,n+1) dp[i][0]=0;
	rep(i,0,m+1) dp[0][i]=0;
	
	
	
	rep(i,1,m+1)
	{
		
		rep(j,1,n+1)
		{
			if(s[j-1]==t[i-1])
			dp[j][i]=1+dp[j-1][i-1];
			else
			dp[j][i]=max(dp[j][i-1],dp[j-1][i]);
		}
	}
	int j=n;
	string ss="";
	for(int i=m;i>0&&j>0;)
	{
		if(s[j-1]==t[i-1])
		{
			j--;
			ss=t[i-1]+ss;
			i--;
		}
		else if(dp[j-1][i]==dp[j][i])
		{
			j--;
			
		}
		else i--;
	}
	
	cout<<ss<<endl;	
	//cout<<dp[n][m];
	
}

Measured memory_bytes: 70656
def is_month( n :int ):
  return ( 1 <= n ) and ( n <= 12 )

def judge( first, second ):
  if (first and second):
    return "AMBIGUOUS"
  elif (first and not(second)):
    return "MMYY"
  elif (not( first ) and second):
    return "YYMM"
  else:
    return "NA"

s = input()
first = is_month( int( s[0:2] ))
second = is_month( int( s[2:4] ))
print( judge( first, second ) )

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

using namespace std;
#define ll long long
#define ld long double
#define f first
#define s second
const int N = 3e3+5;
ll n , s , a[N] , dp[N][N] , suf[N] , pre[N] , mod = 998244353;

int mul(int a, int b)
{
    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return (1ll * a * b) % mod;
}

int add(int a, int b)
{
    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return (a + b) % mod;
}

int solve(int i , int sum)
{
    if (i==0) return sum == s;
    if (sum > s) return 0;

    if (sum == s) return i+1;

    if (dp[i][sum] != -1)
        return dp[i][sum];

    int ans = solve(i-1 , sum);
    ans = add(ans , solve(i-1 , sum+a[i]));

    return dp[i][sum] = ans;
}

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

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

    memset(dp , -1 , sizeof(dp));

    ll ans = 0;
    for(int i=1; i<=n; i++)
    {
        pre[i] = solve(i-1 , a[i]);
        ans = add(ans , mul(n-i+1 , pre[i]));
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 71040
n = int(input())
list_prob = []
for i in range(n-1):
    list_prob.append(list(map(int, input().split())))

for i in range(n-1):
    j = i
    ans = 0
    ans += list_prob[j][1]
    ans += list_prob[j][0]
    j += 1
    while j < n-1:
        if ans < list_prob[j][1]:
            ans = list_prob[j][1]
        else:
            if ans % list_prob[j][2] != 0:
                ans += (list_prob[j][2] - (ans % list_prob[j][2]))
            else:
                pass
        ans += list_prob[j][0]
        j += 1
    print(ans)
print(0)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(x)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> T& chmin(T &a, const U &b){return a = (a<=b?a:b);}
template <typename T, typename U> T& chmax(T &a, const U &b){return a = (a>=b?a:b);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

vector<int> compose(const vector<int> &p, const vector<int> &q){
  int n = p.size();
  vector<int> ret(n);
  REP(i,n) ret[i] = p[q[i]];
  return ret;
}

vector<int> inverse(const vector<int> &p){
  int n = p.size();
  vector<int> ret(n);
  REP(i,n) ret[p[i]] = i;
  return ret;
}

template <typename T> T power(T n, LLI p, const T &e, const function<T(T,T)> &f){
  T ret = e;
  while(p>0){
    if(p&1) ret = f(ret, n);
    n = f(n, n);
    p /= 2;
  }
  return ret;
}

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

  int N,K;
  while(cin >> N >> K){
    vector<int> p(N), q(N); cin >> p >> q;
    for(auto &x : p) --x;
    for(auto &x : q) --x;
    
    auto ip = inverse(p);
    auto iq = inverse(q);
    auto x = compose(q, compose(ip, compose(iq, p)));;
    auto id = vector<int>(N);
    REP(i,N) id[i] = i;
    
    vector<int> as[6] = {id, id, id, q, compose(q,ip), compose(q,ip)};
    vector<int> a = compose(power<vector<int>>(x, (K-1)/6, id, compose), as[(K+5)%6]);
    
    vector<int> bs[6] = {p,q,compose(q,ip),ip,iq,compose(iq,p)};
    auto b = bs[(K+5)%6];
    
    auto ans = compose(a, compose(b, inverse(a)));

    for(auto &x : ans) ++x;
    join(cout, ALL(ans));
  }
  
  return 0;
}


Measured memory_bytes: 9808
#include <bits/stdc++.h>
using namespace std;
const int N=200050,mo=1e9+7;
struct date{
  int x,v;
  bool operator < (const date &c) const {
    if (v!=c.v) return v<c.v;
    return x<c.x;
  }
}q[N];
int le[N],ri[N],st[N],tot,f[N];
int check(int x){
  int l=1,r=tot,mid,ans=x;
  while(l<=r){
    mid=(l+r)>>1;
    if (q[st[mid]].x>q[x].x) r=mid-1,ans=st[mid];
    else l=mid+1;
  }
  return ans;
}
int main(){
  int n; cin>>n;
  for (int i=1; i<=n; ++i) scanf("%d%d",&q[i].x,&q[i].v);
  sort(q+1,q+n+1);
  for (int i=1; i<=n; ++i){
    le[i]=check(i);
    if (!tot||q[i].x>q[st[tot]].x) st[++tot]=i;
  }
  tot=0;
  for (int i=n; i>=1; --i){
    q[i].x=-q[i].x;
    ri[i]=check(i);
    if (!tot||q[i].x>q[st[tot]].x) st[++tot]=i;
  }
  for (int i=1; i<=n; ++i)
    q[i]=(date){le[i],ri[i]};
  sort(q+1,q+n+1);
  f[1]=1;
  for (int i=1,t=1; i<=n; ++i){
    (f[i+1]+=f[i])%=mo;
    while(q[t].v==i&&t<=n){
      int l=q[t].x;
      (f[i+1]+=(mo-f[l-1]+f[i+1])%mo)%=mo;
      ++t;
    }
  }
  cout<<(mo+f[n+1]-f[n])%mo;
  return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
  int n,x;
  cin>>n>>x;
  vector<int> a(n);
  REP(i,n) cin>>a[i];

  sort(ALL(a));
  int ans=0;
  REP(i,n){
    x-=a[i];
    if(x<0) break;
    ans++;
  }
  if(x>0) ans--;
  cout<<ans<<endl;
  
	return 0;
}

Measured memory_bytes: 256
N,K = map(int, input().split())
A = input().split()
A = [int(i) for i in A]
if N/K > 1:
    if(N-K)%(K-1) == 0:
        print(1 + (N-K)//(K-1) )
    else:
        print(1 + (N-K)//(K-1) + 1)
else:
    print(1)

Measured memory_bytes: 13880
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 1e9 + 7;

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

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    string s[50];
    REP(i,H) cin >> s[i];
    REP(i,H){
        REP(j,W){
            if(s[i][j]=='.'){
                int cnt = 0;
                REP(k,8){
                    int nx = j + dx[k];
                    int ny = i + dy[k];
                    if(0<=nx && nx<W && 0<=ny && ny<H && s[ny][nx]=='#') ++cnt;
                }
                s[i][j] = cnt + '0';
            }
        }
    }
    REP(i,H) cout << s[i] << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> path;
vector<bool> visited;

int dfs(int v) {
    visited[v] = true;
    int ret = 0;
    for (int sv : path[v]) {
        if (visited[sv]) continue;
        ret ^= (dfs(sv) + 1);
    }
    return ret;
}

int main() {
    int N;
    cin >> N;

    path.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        path[x].push_back(y);
        path[y].push_back(x);
    }

    visited.assign(N, false);
    cout << (dfs(0) > 0 ? "Alice" : "Bob") << endl;
    return 0;
}


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

using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    const int inf = 1e9+7;
    vector<int> dp(n + k, inf);
    dp[0] = 0;
    rep(i, n) {
        rep(j, k) dp[i+j+1] = min(dp[i+j+1], dp[i]+abs(h[i+j+1] - h[i]));
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 3972
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var move = xArray("[]",6);
var set = new Set([0]);

console.log(main());
function main(){
  var n = o.a();
  for(var i = 0; i < n; i++){
    var x = o.a();
    var y = o.a();
    var d = o.a(1);
    if(d === "U"){
      solve(0,y);
      solve(5,x);
    }else if(d === "R"){
      solve(1,x);
      solve(4,y);
    }else if(d === "D"){
      solve(2,y);
      solve(5,x);
    }else{
      solve(3,x);
      solve(4,y);
    }
  }
  calc(move[0][1],move[4][1],move[2][1]);
  calc(-move[2][0],-move[4][0],-move[0][0]);
  calc(move[1][1],move[5][1],move[3][1]);
  calc(-move[3][0],-move[5][0],-move[1][0]);
  var ans = 1e18;
  for(var i of set){
    var u = max(move[0][1]+i,move[2][1]-i,move[4][1]);
    var d = min(move[0][0]+i,move[2][0]-i,move[4][0]);
    var r = max(move[1][1]+i,move[3][1]-i,move[5][1]);
    var l = min(move[1][0]+i,move[3][0]-i,move[5][0]);
    var s = (u-d)*(r-l);
    if(s < ans)ans = s;
  }
  return ans;
}

function solve(i,z){
  if(move[i].length){
    if(move[i][0] > z)move[i][0] = z;
    else if(move[i][1] < z)move[i][1] = z;
  }else{
    move[i][0] = move[i][1] = z;
  }
}

function calc(u,x,d){
  set.add(Math.max(0,(d-x)||0));
  set.add(Math.max(0,((d-u)/2)||0));
  set.add(Math.max(0,(x-u)||0));
}

function max(){
  var a = arguments;
  var r = a[0];
  for(var i = 1; i < a.length; i++){
    if(isNaN(a[i]))continue;
    if(r>a[i])continue;
    r = a[i];
  }
  return r;
}

function min(){
  var a = arguments;
  var r = a[0];
  for(var i = 1; i < a.length; i++){
    if(isNaN(a[i]))continue;
    if(r<a[i])continue;
    r = a[i];
  }
  return r;
}

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int H, W; cin >> H >> W;
        vector<vector<string>> G(H, vector<string>(W));
        rep(i, H) cin >> G[i];
        rep(y, H) rep(x, W) {
            if(G[y][x] == "snuke") {
                string a = "A";
                a[0] += x;
                cout << a << y + 1 << endl;
                return 0;
            }
        }
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def f(y):
    cnt  = 0
    tmp = y
    while tmp:
        tmp = tmp%popcnt(tmp)
        cnt += 1
    return cnt

n = int(input())
x = list(input())

cc = 0
for e in x:
    if e == '1':
        cc += 1

if cc == 0:
    for i in range(n):
        print(1)
    exit()
if cc == 1:
    p = 1
    q = 1
    #xをccで割った時の余り
    s = 0
    #xをcc-1で割った時の余り
    t = 0

    for i in range(n-1,-1,-1):
        if x[i] == '1':
            s = (s+p)%(cc+1)
        p = p*2%(cc+1)




    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((s+pow(2,n-1-i,cc+1))%(cc+1))+1)
        
    exit()


p = 1
q = 1
#xをccで割った時の余り
s = 0
#xをcc-1で割った時の余り
t = 0

for i in range(n-1,-1,-1):
    if x[i] == '1':
        s = (s+p)%(cc+1)
        t = (t+q)%(cc-1)
    p = p*2%(cc+1)
    q = q*2%(cc-1)



for i in range(n):
    if x[i] == '1':
        print(f((t-pow(2,n-1-i,cc-1))%(cc-1))+1)
    else:
        print(f((s+pow(2,n-1-i,cc+1))%(cc+1))+1)
    




Measured memory_bytes: 86276
#include <stdio.h>

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

  int ans = x + n;
  for(int i=0; i<n; i++){
    int t;  scanf("%d", &t);
    ans = ans + (d-1)/t;
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, w = ns()
    w_list = []
    v_list = []
    for _ in range(n):
        wi, vi = ns()
        w_list.append(wi)
        v_list.append(vi)

    lim = 301
    base = w_list[0]
    dp = [[-1] * (lim + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for wi, vi in zip(w_list, v_list):
        wi -= base
        for i in range(n - 1, -1, -1):
            base_cost = (i + 1) * base
            for j in range(lim + 1):
                if dp[i][j] != -1:
                    if j + wi + base_cost <= w:
                        dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)

    ans = 0
    for dpi in dp:
        ans = max(ans, max(dpi))

    print(ans)


if __name__ == '__main__':
    main()


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

int main()
{
	double n;
	double c[12];

	c[0] = 128;
	for(int i=1; i<12; i++)
	{
		c[i] = c[i-1]/2;
	}

	while(cin >> n, n>=0)
	{
		int a[12] = {0};

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

		if(!n)
		{
			for(int i=0; i<12; i++)
			{
				cout << a[i];
				if(i==7) cout << '.';
			}
			cout << endl;
		}
		else
		{
			cout << "NA" << endl;
		}
	}
}

Measured memory_bytes: 0
program abc160c2
      implicit none
      integer::K,N,i,maxA,x,y,index,Cmin=0
      integer,allocatable,dimension(:)::A

        read *,K,N
        allocate(A(N))
        read *,A

        maxA=0
        do i=1,N-1
           x=A(i+1)-A(i)
           if (maxA<x) then
              maxA=x
              index=i
           end if
        end do
        y=K-A(N)+A(1)
        if (maxA<y) then
           maxA=y
           index=0
        end if

        do i=1,N-1
           if (i==index) cycle
           Cmin=Cmin+(A(i+1)-A(i))
        end do

        if (index/=0) then
           Cmin=Cmin+(K-A(N)+A(1))
        end if

        print *,Cmin
        stop

   end program abc160c2

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
const ll MOD = 1000000007;

int main() {
	int X;
	cin >> X;
	if (X > 29) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3628
/*author: hyperion_1724
  date: 
*/

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define veci vector<int>
#define vecl vector<long long>
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

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

	READV(N);
	READV(K);
	vecl dp(K+1,0);
	dp[0]=1;
	FORI(i,0,N)
	{
		READV(A);
		vecl dp1(K+1,0);
		FORI(j,0,K+1)
		{
			if (dp[j]!=0)
			{
				dp1[j]=(dp1[j]+dp[j])%MOD;
				if (j+A+1<=K)
				{
					dp1[j+A+1]=(dp1[j+A+1]+MOD-dp[j])%MOD;
				}
			}
		}
		FORI(j,1,K+1)
		{
			dp1[j]=(dp1[j]+dp1[j-1])%MOD;
		}
		dp=dp1;
	}
	cout<<dp[K]<<endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#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=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int k;
    cin >> k;
    if (k == 1){
        cout << 1 << endl << 1 << endl;
        return 0;
    }
    int n = (k + 3) / 4 * 2;
    VVI ans(n, VI(n));
    REP(i,n) REP(j,n){
        ans[i][j] = ((i + j) % n) + 1 + n * (i % 2);
        if (ans[i][j] > k) ans[i][j] -= n;
    }

    cout << n << endl;
    REP(i,n){
        REP(j,n) cout << ans[i][j] << " ";
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 2176
fun main(args: Array<String>) {
    val (n,w) = readLine()!!.split(" ").map { it.toInt() }
    val wv = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
    val w1 = wv[0][0]+0L

    val items = Array(4){ i ->
        intArrayOf(0, *(wv.filter { it[0]+0L==w1+i }.map { it[1] }.sortedDescending().toIntArray()) )}
    items.forEach { for(i in 1..it.lastIndex) it[i]+=it[i-1] }

    var max = 0
    for(i0 in 0..items[0].lastIndex){
        for(i1 in 0..items[1].lastIndex) {
            for (i2 in 0..items[2].lastIndex) {
                for (i3 in 0..items[3].lastIndex) {
                    if(w1*i0+(w1+1)*i1+(w1+2)*i2+(w1+3)*i3<=w) {
                        max = Math.max(max, items[0][i0] + items[1][i1] + items[2][i2] + items[3][i3])
                    }
                }
            }
        }
    }
    println(max)
}

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

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int kusim[]=new int[2*n];
		int ans=0;

		for(int i=0;i<2*n;i++){
			kusim[i]=sc.nextInt();
		}

		int turn=kusim.length-1;
		for(int j=0;j<turn;j++){
			for(int k=0;k<turn-j;k++){
				if(kusim[k]>kusim[k+1]){
					int a=kusim[k];
					kusim[k]=kusim[k+1];
					kusim[k+1]=a;
				}
			}
		}

		for(int l=0;l<n;l++){
			ans+=kusim[2*l];
		}

		System.out.println(ans);
	}

}

Measured memory_bytes: 9684
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <vector>
#include <array>
#include <set>
#include <climits>
#include <sstream>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <numeric>
using namespace std;
using namespace __gnu_pbds;
typedef tree< // find_by_order & order_of_key
        int ,
        null_type ,
        less<int> ,
        rb_tree_tag ,
        tree_order_statistics_node_update 
> new_set;
#define MOD 1000000007

int main(void){
#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    freopen("error","w",stderr);
#endif 
    int n, k;
    scanf("%d %d",&n,&k);
    vector<int>v(n) , dp(n+1 , INT_MAX);
    for(auto&itr:v){
        cin>>itr;
    }
    dp[0] =0;
    for(int i=0; i < n; ++i ) {
        for( int j=i+1; j < i+k+1 && j<n; ++j ){ 
            dp[j] = min(dp[j] , dp[i]+abs(v[i]-v[j]));
        }
    }
    cout << dp[n-1] << '\n';
    return 0;
}


Measured memory_bytes: 1024
n = gets.to_i
a = gets.chomp().split(' ').map(&:to_i)

th = 10**18
s = 1
if a.include?(0)
        puts 0
        exit
end

a.each do |i|
        s = s*i
        if s > th
                puts -1
                exit
        end
end
puts s

Measured memory_bytes: 23524
#include <stdio.h>
int main()
{
    int a, b, c, k;
    int result;
    scanf("%d %d %d %d", &a, &b, &c, &k);
    if (k <= a)
    {
        result = k;
    }
    else if (k <= (a + b))
    {
        result = a;
    }

    else
    {
        result = a - (k - (a + b));
    }

    printf("%d", result);

    return 0;
}

Measured memory_bytes: 1704
import java.util.*;
 
public class Main{

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] a = new int[N];
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < N; i++){
            a[i] = sc.nextInt();
            if(1 <= a[i] && a[i] <= 399){
                map.put("grey", 1);
            } else if(a[i] <= 799){
                map.put("brown", 1);
            } else if(a[i] <= 1199){
                map.put("green", 1);
            } else if(a[i] <= 1599){
                map.put("mizu", 1);
            } else if(a[i] <= 1999){
                map.put("blue", 1);
            } else if(a[i] <= 2399){
                map.put("yellow", 1);
            } else if(a[i] <= 2799){
                map.put("orange", 1);
            } else if(a[i] <= 3199){
                map.put("red", 1);
            } else {
                if(map.containsKey("all"))
                    map.put("all", map.get("all") + 1);
                else
                    map.put("all", 1);
            }
        }
        sc.close();

        int min = 0;
        int max = 0;
        if(map.size() == 1 && !(map.containsKey("all"))){
            min = 1;
            max = 1;
        } else if(map.size() == 1){
            min = 1;
            max = map.get("all");
        }else{
            for(String key: map.keySet()){
                if(key.equals("all")){
                    max += map.get(key);
                } else {
                    min += map.get(key);
                    max += map.get(key);
                }
            }
        }
        System.out.println(min + " " + max);
    }
}

Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define fr(i,n) for(int i=0;i<(n);i++)
#define Fr(i,n) for(int i=0;i++<(n);)
#define ifr(i,n) for(int i=(n)-1;i>=0;i--)
#define iFr(i,n) for(int i=(n);i>0;i--)

int main(){
    ll r,d,x;
    cin>>r>>d>>x;
    fr(i,10){
        x=r*x-d;
        cout<<x<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);i++)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;i--)
#define lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T mpow(T a, T n) {
   T res = 1;
   for(;n;n>>=1) {
      if (n & 1) res = res * a;
      a = a * a;
   }
   return res;
}

//cin.tie(0);ios::sync_with_stdio(false);



signed main()
{
  int t;cin>>t;
  while(t--){
    ll a,b,c,d,g;cin>>a>>b>>c>>d;
    g=gcd(b,d);
    if(d<b || a<b){
      cout<<"No"<<endl;
    }else if(a-g*((a-c-1)/g)<b){
      //cout<<a-g*((a-c-1)/g)<<endl;
      cout<<"No"<<endl;
    }else{
      cout<<"Yes"<<endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    
#define int long long
    
#define REP(i,n) for(int i=0;i<n;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 pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 99999999999
    
using namespace std;
    
int dy[4]={1, -1, 0, 0};
int dx[4]={0, 0, 1, -1};

int32_t main(){
    int n, m;
    cin >> n >> m;

    if(n==1 && m==1){
        cout << 1 << endl;
    }
    else if(n==1){
        cout << m-2 << endl;
    }
    else if(m==1){
        cout << n-2 << endl;
    }
    else{
        cout << (n-2)*(m-2) << endl;
    }
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::iter;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::usize;

#[allow(unused_macros)]
macro_rules! read_cols {
    ($($t:ty),+) => {{
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();

        let mut it = line.trim()
            .split_whitespace();

        ($(
            it.next().unwrap().parse::<$t>().ok().unwrap()
        ),+)
    }}
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn root(g: &mut Vec<usize>, i: usize) -> usize {
    if g[i] != i {
        let parent = g[i];
        g[i] = root(g, parent);
    }
    g[i]
}

fn merge(g: &mut Vec<usize>, i: usize, j: usize) {
    let lg = root(g, i);
    let rg = root(g, j);
    
    g[rg] = lg;
}

fn main() {
    let (n, m) = read_cols!(usize, i64);
    
    let v = {
        let mut v = vec![];
        for _ in 0..n {
            v.push(read_cols!(i64, i64));            
        }
        v.sort();
        v
    };
    
    let s = v.into_iter().scan((0, 0), |s, (a, b)| {
        s.0 += a * b;
        s.1 += b;
        Some((s.0, s.1, a, b))
    }).take_while(|s| s.1 - s.3 < m).last().unwrap();

    let ans = s.0 + (m - s.1) * s.2;
    println!("{}", ans);
}


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

int main() {
    ll n;
    cin>>n;
    vector<ll> h(n);
    rep(i,n)cin>>h[i];
    ll before=h[n-1];
    for(ll i=n-2;i>=0;i--){
        if(h[i]>before){
            h[i]--;
            if(h[i]>before){
                cout<<"No"<<endl;
                return 0;
            }
        }
        before=h[i];
    }
    cout<<"Yes"<<endl;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
    int N, M; cin >> N >> M;
    vector<int> a(M), b(M); rep(i, M) cin >> a[i] >> b[i];

    map<int, int> res; rep(i, N) res[i] = 0;
    rep(i, M) {
        res[a[i] - 1]++;
        res[b[i] - 1]++;
    }

    rep(i, N) {
        cout << res[i] << endl;
    }
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, N):
        self.N = N
        self.par = [n for n in range(N)]
        self.rank = [1] * N
        
    def find(self, u):
        if self.par[u] == u:
            return u
        else:
            return self.find(self.par[u])
    
    def union(self, u, v):

        pu = self.find(u)
        pv = self.find(v)

        if pu == pv: 
            return

        if self.rank[pu] < self.rank[pv]:
            self.par[pu] = pv
            self.rank[pv] += self.rank[pu]

        else: # self.rank[pu] > self.rank[pv]
            self.par[pv] = pu
            self.rank[pu] += self.rank[pv]
 
N, M = map(int, input().split())
UF = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    UF.union(A, B)


ret = 0

for n in range(N):
    ret = max(ret, UF.rank[n])

print(ret)


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

const int INF = 1001001001;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

void solve() {
  int n, k;
  cin >> n >> k;
  vi32 a(n);
  cin >> a;
  while (k--) {
    auto p = a;
    a.assign(n, 0);
    rep(i, n) {
      int l = max(0, i - p[i]);
      int r = min(n, i + p[i] + 1);
      a[l] += 1;
      if (r < n) a[r] -= 1;
    }
    rep(i, n - 1) a[i + 1] += a[i];
    if (a == p) {
      break;
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 4936
#include <algorithm>
#include <iostream>
#include <limits>
#include <tuple>

using namespace std;

int main()
{
    bool first = false;
    while (true) {
        int cost;
        cin >> cost;
        if (cost == 0) {
            return 0;
        }
        if (first) {
            cout << endl;
        }

        int n10, n50, n100, n500;
        cin >> n10 >> n50 >> n100 >> n500;

        auto changeCoins = [](int n) {
            int nn500 = n / 500;
            n %= 500;
            int nn100 = n / 100;
            n %= 100;
            int nn50 = n / 50;
            n %= 50;
            int nn10 = n / 10;
            return make_tuple(nn10, nn50, nn100, nn500);
        };

        auto numberOfCoins = [](const auto &t) {
            int x, y, z, w;
            tie(x, y, z, w) = t;
            return x + y + z + w;
        };

        auto min_ =
            make_tuple(numeric_limits<int>::max(), numeric_limits<int>::max(),
                       numeric_limits<int>::max(), numeric_limits<int>::max(),
                       numeric_limits<int>::max());
        for (int i = 0; i <= n10; ++i) {
            for (int j = 0; j <= n50; ++j) {
                for (int k = 0; k <= n100; ++k) {
                    for (int l = 0; l <= n500; ++l) {
                        const int sum = i * 10 + j * 50 + k * 100 + l * 500;
                        if (sum < cost) {
                            continue;
                        }
                        const auto change = sum - cost;
                        const auto t = changeCoins(change);
                        if (t == make_tuple(i, j, k, l)) {
                            continue;
                        }
                        auto remainNumberOfCoins = numberOfCoins(t) +
                                                   (n10 - i) + (n50 - j) +
                                                   (n100 - k) + (n500 - l);
                        if (remainNumberOfCoins < get<0>(min_)) {
                            min_ = make_tuple(remainNumberOfCoins, i, j, k, l);
                        }
                    }
                }
            }
        }
        int x, y, z, w;
        tie(ignore, x, y, z, w) = min_;
        if (x != 0) {
            cout << 10 << ' ' << x << endl;
        }
        if (y != 0) {
            cout << 50 << ' ' << y << endl;
        }
        if (z != 0) {
            cout << 100 << ' ' << z << endl;
        }
        if (w != 0) {
            cout << 500 << ' ' << w << endl;
        }
        first = true;
    }
}


Measured memory_bytes: 3072
//#include<cstdio>
//using namespace std;
//int main()
//{
//    int a,b;
//    scanf("%d%d",&a,&b);
//    printf("%d",a-2*b>=0?(a-2*b):0);
//    return 0;
//}
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include<ctime>
using namespace std;
const int maxn = 50;
long long a[maxn];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			ans += a[i] * a[j];
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    string N_str;
    N_str = to_string(N);

    if ((int) N_str.find("7")>=0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3680
alp = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

y = int(input())

ans = []
while y > 26:
    res = y%26
    if res == 0:
        ans.append(25)
        y = y//26 - 1
    else:
        ans.append(y%26 - 1)
        y = y // 26
ans.append(y - 1)
ans = ans[::-1]
S = ''
for i in range(len(ans)):
    S += alp[ans[i]]
print(S)

Measured memory_bytes: 9212