akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<long long, long long>
#define f first
#define s second
#define debug cout<<"here\n" 
#define MOD 1000000009

const int MAXN = 2e5 +15;
 
using namespace std;

void solve(){    
    ll x,k,d; cin>>x>>k>>d;
    x = abs(x);
    if(k < (x/d)) cout<<x-k*d;
    else{
        k -= (x/d);
        x -= (x/d)*d;
        if(k%2) cout<<d-x;
        else cout<<x;
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);    
    cout<<fixed<<setprecision(12);

    int t =1; //cin>>t;
    for(int i=1; i<= t; i++){
        solve();
        cout<<"\n";
    }
    
    return 0;
}   

Measured memory_bytes: 3656
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int):
    if N==M:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,a) FOR(i,0,(int)(a)-1)
#define reset(a,b) memset(a,b,sizeof(a))
#define BUG(x) cout << #x << " = " << x << endl
#define PR(x,a,b) {cout << #x << " = "; FOR (_,a,b) cout << x[_] << ' '; cout << endl;}
#define CON(x) {cout << #x << " = "; for(auto i:x) cout << i << ' '; cout << endl;}
#define mod 1000000007
#define pi acos(-1)
#define eps 0.00000001
#define pb push_back
#define sqr(x) (x) * (x)
#define _1 first
#define _2 second

int n, m, edge[11][11], dp[1111][11];
int u, v;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  REP (i, m) {
  	cin >> u >> v;
  	u--; v--;
  	edge[u][v] = edge[v][u] = 1;
  }
  dp[1][0] = 1;
  FOR (mask, 2, (1 << n) - 1) REP (i, n) if (mask & (1 << i)) {
  	REP (j, n) if (i != j) if (mask & (1 << j)) if (edge[i][j]) dp[mask][i] += dp[mask ^ (1 << i)][j];
  }
  int ans = 0;
  REP (i, n) ans += dp[(1 << n) - 1][i];
  // REP (i, n) cout << i << ' ' << dp[(1 << n) - 1][i] << endl;
  cout << ans;
}

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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)

const i32 M = 998244353;
i32 dp[90310];
i32 dq[90310];

signed main() {
  i32 n;
  scanf("%d", &n);
  i32 sum = 0;
  i32 ans = 1;
  dp[0] = 1;
  dq[0] = 1;
  REP(i, n) {
    i32 a;
    scanf("%d", &a);
    RREP(t, sum + 1) {
      (dp[t + a] += dp[t]) %= M;
      (dp[t] *= 2) %= M;
      (dq[t + a] += dq[t]) %= M;
    }
    sum += a;
    ans = (ans * 3) % M;
  }
  i32 lim = (sum - 1) / 2;
  FOR(t, lim + 1, sum + 1) {
    ans = (ans - dp[t] * 3) % M;
  }
  if (sum % 2 == 0) {
    ans = (ans + dq[sum / 2] * 3) % M;
  }
  ans = (ans + M) % M;
  printf("%d\n", ans);
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main(){

int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  
  if(e - a <= k) cout << "Yay!" << endl;
  else cout << ":(" << endl;
  return 0;
  
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  if (w >= v) {
    cout << "NO" << endl;
    return 0;
  }
  ll dist = abs(a-b), x = v-w;
  if (x*t >= dist)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3660
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main(void){
	
	long long int n,three,five,fift,sum = 0,sum3,sum5,sum15;
	scanf("%ld", &n);
	if(n%3 == 0 ) three = n;
	else three = n-(n%3);
	if(n%5 == 0 ) five = n;
	else five = n-(n%5);
	if(n%15 == 0 ) fift = n;
	else fift = n-(n%15);
	sum3 = ((three/3)*(6+((three/3)-1)*3))/2;
	sum5 = ((five/5)*(10+((five/5)-1)*5))/2;
	sum15 = ((fift/15)*(30+((fift/15)-1)*15))/2;
	sum = n*(1+n)/2-sum3-sum5+sum15;
	
	printf("%ld", sum);
	
}

Measured memory_bytes: 1732
N = int(input())

L = [0] * (N)

def prime_factorize(n):
  i = 2
  p_nums = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      p_nums.append(i)
    i += 1
  if n > 1:
    p_nums.append(n)
  return p_nums

for i in range(1,N + 1):
  P = prime_factorize(i)
  for j in range(len(P)):
    p = int(P[j])
    L[p - 1] += 1
    
total = 1
    
for i in L:
  if i != 0:
    total *= (i + 1)
    
div = 10 ** 9 + 7
  
print(total % div)


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var X = line[1];
            var x = consoleReader.SplitInt().Select(a => Math.Abs(a - X)).ToArray();

            return Gcd(x);
        }
        int Gcd(int a, int b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b));
        int Gcd(params int[] nums)
        {
            var gcd = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                gcd = Gcd(nums[i], gcd);
            }
            return gcd;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Measured memory_bytes: 21088
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function getcod(cod,lim)
    if cod==0 || cod==lim+1
        return false
    else
        return true
    end
end

function main()
    s=chomp(readline())
    println(700+100*count(x->x=='o',s))
end
main()

Measured memory_bytes: 110444
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v(5);
    vector<int> d(5);
    int skip = 0;
    int maxi = 0;
    for(int i = 0; i < 5; i++)
    {
        cin >> v[i];
        d[i] = (v[i] % 10 != 0) * (10 - (v[i] % 10));
        if(d[i] > maxi)
        {
            maxi = d[i];
            skip = i;
        }
    }
    for(int i = 0; i < 5; i++) if(i != skip) v[i] += d[i];
    cout << accumulate(v.begin(), v.end(), 0);

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef long long int ll;
ll n,k,ans;
int main(){
	scanf("%lld%lld",&n,&k);
	ll div=n/k;
	ans+=div*div*div;
	if(k%2==0){
		if((n-div*k)>=k/2){
			div++;
			ans+=div*div*div;
		}else{
			ans+=div*div*div;
		}
	}
	printf("%lld",ans);
} 

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


int main_B() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    vi a(1000010, 0);
    cin >> a[1];

    int i = 2;
    set<int> st;
    st.insert(a[1]);
    int ans;
    while(true){
        if (a[i - 1]%2 == 0) {
            a[i] = a[i - 1] / 2;
        } else {
            a[i] = 3 * a[i - 1] + 1;
        }
        
        if (st.count(a[i])>0) {
            ans = i;
            break;
        }

        st.insert(a[i]);
        i++;
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
#include<queue>
#include<map>

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    vector<pair<int, int>> vp;
    for(int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
        vp.emplace_back(a, b);
    }
    map<pair<int, int>, int> I;
    vector<int> cs(n, 0);
    vector<int> used(n, 0);
    queue<int> que;

    used[0] = 1;
    que.emplace(0);
    int k = 0;
    while(!que.empty()) {
        int v=que.front();que.pop();
        if(k<(int)g[v].size()) k=g[v].size();   // 色の最大数の更新
        // 色の決定
        int cur=1;
        for(int u:g[v]) { 
            if(used[u]) continue;
            if(cur==cs[v]) cur++;
            cs[u] = I[make_pair(u, v)] = I[make_pair(v, u)]=cur++;
            used[u]=1;
            que.emplace(u);
        }
    }

    // 出力
    cout << k << endl;
    for(auto p:vp) cout << I[p] << endl;
}

Measured memory_bytes: 20084
#include<bits/stdc++.h>
#define re register
#define ui unsigned int
#define ull unsigned long long
const int B=1<<9,mod=1e9+7;
int bb[(1<<18)+1],bs[(1<<18)+1],p[(1<<18)+1],inv[(1<<18)+1],val[(1<<18)+1],vai[(1<<18)+1],ll[(1<<18)+1],rr[(1<<18)+1],h,n,N;
void add(re int a,re int ad)
{
	for(re int i=a;i<a/B*B+B;i++)bb[i]=(bb[i]+ad)%mod;
	for(re int i=a/B+1;i<(1<<8);i++)bs[i]=(bs[i]+ad)%mod;
}
inline int qry(re int a)
{
	return (bb[a]+bs[a/B])%mod;
}
void dfs(re int a)
{
	val[a]=1ll*val[a]*a%mod;
	if(a<n)
	{
		val[a*2]=val[a*2+1]=val[a];
		vai[a*2]=vai[a*2+1]=1ll*vai[a]*inv[a]%mod*inv[a]%mod;
		dfs(a*2);dfs(a*2+1);
		ll[a]=ll[a*2];rr[a]=rr[a*2+1];
	}
	else ll[a]=rr[a]=a-n;
	vai[a]=1ll*vai[a]*inv[a]%mod;
}
int ans,vc;
void qqp(re int x)
{
	if(x==1)return;
	qqp(x/2);
	x=x^1;
	re int vl=1ll*vc*vai[x/2]%mod;
	ans=(ans+1ll*vl*(qry(rr[x])-(ll[x]?qry(ll[x]-1):0)+mod))%mod;
}
void cal(re int x)
{
	if(x>=n)
	{
		re int vv=vc;
		vc=1ll*vc*val[x]%mod*val[p[x-n]+n]%mod;
		qqp(p[x-n]+n);
		vc=vv;
		return;
	}
	else
	{
		cal(x*2);
		cal(x*2+1);
	}
}
void qqr(re int x)
{
	if(x==1)return;
	vc=vai[x/2];
	cal(x^1);
	if(x%2==1)qqr(x/2);
	else
	{
		vc=(mod-vai[x/2])%mod;
		cal(x);
	}
}
void qqv(re int x)
{
	if(x%2==1)return;
	vc=(mod-vai[x/2])%mod;
	cal(x^1);
	qqv(x/2);
}
int main()
{
	scanf("%d",&h);n=1<<(h-1);N=2*n-1;
	for(re int i=0;i<n;i++)scanf("%d",&p[i]),p[i]--;inv[1]=1;
	for(re int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	val[1]=vai[1]=1;dfs(1);
	for(re int i=0;i<n;i++)
	{
		add(p[i],1ll*val[i+n]*val[p[i]+n]%mod);
		qqr(i+n);
		if(i<n-1)qqv(i+1+n);
	}
	ans=1ll*ans*inv[2]%mod;
	printf("%d\n",ans);
}

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

using ll = long long;
using ull = unsigned long long;
#define repi(n) for (long long i = 0; i < (n); i++)
#define repj(n) for (long long j = 0; j < (n); j++)
#define repk(n) for (long long k = 0; k < (n); k++)
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define itr(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = std::max(t, (v)))
#define updatemin(t, v) (t = std::min(t, (v)))

ll c[20], a[20][20];
int main() {
  ll n, m, x;
  cin >> n >> m >> x;
  repi(n) {
    cin >> c[i];
    repj(m) cin >> a[i][j];
  }
  ll re = LLONG_MAX;
  repi(1ll << n) {
    vector<ll> xs(m, 0);
    ll cost = 0;
    repj(n) {
      if ((i >> j) & 1) {
        cost += c[j];
        repk(m) xs[k] += a[j][k];
      }
    }
    bool valid = true;
    repj(m) if (xs[j] < x) valid = false;
    if (valid) updatemin(re, cost);
  }
  cout << (re == LLONG_MAX ? -1 : re) << endl;
}


Measured memory_bytes: 3624
import sys
input = sys.stdin.readline

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [float("inf")]*(h+1)
dp[0] = 0
for i in range(n):
  a, b = AB[i]
  for j in range(h+1):
    if j <= a:
      dp[j] = min(dp[j], b)
    else:
      dp[j] = min(dp[j], dp[j-a]+b)
print(dp[h])

Measured memory_bytes: 48732
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",a+i);
    }
    long long res=0;
    for(int i=1;i<n;i++)
    {
        res+=((a[i]<a[i-1])*(a[i-1]-a[i]));
        a[i]+=((a[i]<a[i-1])*(a[i-1]-a[i]));
    }
    printf("%lld",res);
  	return 0;
}


Measured memory_bytes: 2496
#include <iostream>
#include <map>
#include <set>
#include <cstring>

using namespace std;

const int N = 10000;
int cnt[N] = { 0 }, ans[N / 2 + 1] = { 0 };

int main(){
	int n;
	while(cin >> n, n) {
		// memset(cnt, 0, sizeof(cnt));
		memset(ans, 0, sizeof(ans));
		set<int> k;
		for(int i = 1;i < n;++i){
			int a = i % n;
			int v = (a * a) % n;
			// cnt[v]++;
			k.insert(v);
		}
		for(auto f = k.begin();f != k.end();++f){
			for(auto b = next(f, 1);b != k.end();++b){
				int diff = (*b - *f);
				// cout << "diff : " << diff << endl;
				if(diff > (n - 1) / 2) {
					diff = n - diff;
				}
				ans[diff] += 2;
			}
		}
		for(int i = 1;i <= (n - 1) / 2;++i){
			cout << ans[i] << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3288
#include<cstdio>

int main(){
	int i,n,cards[4][13]={{}};
	char a;
	int b;
	scanf("%d\n",&n);
    for(i=0;i<n;i++){
		scanf("%c %d\n",&a,&b);
		switch(a) {
			case 'S':
				cards[0][b-1]=1;
				break;
			case 'H':
				cards[1][b-1]=1;
				break;
			case 'C':
				cards[2][b-1]=1;
				break;
			case 'D':
				cards[3][b-1]=1;
				break;
	 			}
	} 
	for(i=0;i<52;i++) {
		switch(i/13) {
			case(0):
				if(cards[0][i%13]==0) printf("S %d\n", i+1);
				break;
			case(1):
				if(cards[1][i%13]==0) printf("H %d\n", i%13+1);
				break;
			case(2):
				if(cards[2][i%13]==0) printf("C %d\n", i%13+1);
				break;
			case(3):
				if(cards[3][i%13]==0) printf("D %d\n", i%13+1);
				break;
					}
		}
}


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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)1e9+7

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

bool IsPrime(int num)
{
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;

  double sqrtNum = sqrt(num);
  for(int i = 3; i <= sqrtNum; i += 2) {
    if(num % i == 0) return false;
  }

  return true;
}

signed main() {
  int q;
  cin >> q;
  int l[100005], r[100005];
  int k[100005] = {};
  rep(i, 0, q) {
    cin >> l[i] >> r[i];
  }
  for(int i = 1; i < 100001; i += 2) {
    if(IsPrime(i) && IsPrime((i + 1) / 2)) k[i] = 1;
  }
  rep(i, 1, 100001) {
    k[i] += k[i - 1];
  }
  rep(i, 0, q) {
    cout << k[r[i]] - k[l[i] - 1] << endl;
  }
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string str = Console.ReadLine();
		string ans = "AC";
		if(str.Substring(0,1) != "A"){
			ans = "WA";
		}
		long ct = 0;
		for(var i=2;i<str.Length-1;i++){
			if(str.Substring(i,1) == "C"){
				ct += 1;
			}
		}
		if(ct != 1){
			ans = "WA";
		}
		string aa = "abcdefghijklmnopqrstuvwxyzC";
		for(var i=1;i<str.Length;i++){
			long cc = 0;
			for(var j=0;j<aa.Length;j++){
				if(str.Substring(i,1) == aa.Substring(j,1)){
					cc = 1;
					break;
				}
			}
			if(cc == 0){
				ans = "WA";
				break;
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
#define ll long long
#define inf(x) (ll)(1e##x)
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
const int N = 101000;
int s[N],dep[N],vis[N],fa[N],n,m,p1,p2,tot,a[N],sum,u[N],v[N];
vector<int> e[N];
void dfs(int x,int dad){
	s[x]=-s[dad];sum+=s[x];dep[x]=dep[dad]+1;
	vis[x]=1;fa[x]=dad;
	for(int v:e[x]) if(v!=dad){
		if(s[v]) p1=x,p2=v;
		else dfs(v,x);
	}
}
void dfs2(int x,int dad){
	vis[x]=1;
	for(int v:e[x]) if(!vis[v])
		dfs2(v,x),s[x]+=s[v];
}
void solve1(){
	if(sum){cout<<-1<<'\n';return;}
	dfs2(1,0);
	int ans=0;
	for(int i=1;i<=n;i++) ans+=abs(s[i]);
	cout<<ans<<'\n';
}
void solve2(){
	if(sum&1){cout<<-1<<'\n';return;}
	s[p1]-=sum/2;s[p2]-=sum/2;
	dfs2(1,0);
	int ans=abs(sum)/2;
	for(int i=1;i<=n;i++) ans+=abs(s[i]);
	cout<<ans<<'\n';
}
void solve3(){
	if(sum){cout<<-1<<'\n';return;}
	if(dep[p1]>dep[p2]) swap(p1,p2);
	dfs2(1,0);
	int ans=0;
	while(p1!=p2) a[++tot]=s[p2],vis[p2]=2,p2=fa[p2];
	for(int i=1;i<=n;i++) if(vis[i]<2) ans+=abs(s[i]);
	a[++tot]=0;
	sort(a+1,a+tot+1);
	int k=a[tot+1>>1];
	for(int i=1;i<=tot;i++) ans+=abs(a[i]-k);
	cout<<ans<<'\n';
}
int main(){
	read(n);read(m);
	for(int i=1;i<=m;i++){
		read(u[i]);read(v[i]);
		e[u[i]].push_back(v[i]);
		e[v[i]].push_back(u[i]);
	}
	s[0]=-1;dfs(1,0);
	memset(vis,0,sizeof(vis));
	if(m==n-1){solve1();return 0;}
	if(s[p1]==s[p2]){solve2();return 0;}
	else {solve3();return 0;}
	return 0;
}

Measured memory_bytes: 13184
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long intS
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    
    int n;
    
    cin >> n ;
    
    if (n<1000){
    
    cout << "ABC" << endl;
    
    }else {
    
    cout << "ABD" << endl;
    
    }
    
    
//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
n = int(input())

max4 = n // 4 + 1
max7 = n // 7 + 1

check = False
for i in range(max4):
    for j in range(max7):
        s = 4 * i + 7 * j
        if s == n:
            check = True
            break

if(check):
    print('Yes')
else:
    print('No')



Measured memory_bytes: 2940
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){

    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

bool IsPrime(ll num){
    if(num < 2) return false;
    else if(num == 2) return true;
    else if(num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for(ll i = 3; i <= sqrtNum; i += 2){
        if(num%i==0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

signed main(){
  int n; cin>>n;
  string a,b; cin>>a>>b;
  // int n = a.size();
  string ans = "";
  rep(i,n){
    ans = ans + a[i];
    ans = ans + b[i];
  }
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
program atcoder
    implicit none
    character(30) s
    integer ans,k,i,l
    read(*,*)s
    l = len_trim(s)
    ans = 100000000
    do i=1,l-2
        read(s(i:i+2),*)k
        ans = min(ans,abs(753-k))
    enddo
    write(*,'(I0)')ans
!----------------------functions--------------------------
contains



end program atcoder

Measured memory_bytes: 256
N, K = gets.split.map(&:to_i)
H = gets.split.map(&:to_i)
dp = Array.new(N, Float::INFINITY)
dp[0] = 0
(1 ... N).each do |i|
  dp[i] = ([i - K, 0].max ... i).map{|j| dp[j] + (H[j] - H[i]).abs }.min
end
puts dp[-1]


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




int main(){
	
	string s,t;
	cin>>s>>t;
	if(s.size()+1!=t.size()){
		cout<<"No";
		return 0;
	}
	string k = t.substr(0,s.size());
	if(s!=k){
		cout<<"No";
		return 0;
	}
	cout<<"Yes";
}



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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const int MAX = 1000000;

bool isa[MAX + 1], isb[MAX + 1];

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n, m; cin >> n >> m;
    vector<ll> a(n);
    vector<ll> b(m);
    for(int i=0;i<n;i++){
        cin >> a[i];
        isa[a[i]] = true;
    }
    for(int i=0;i<m;i++){
        cin >> b[i];
        isb[b[i]] = true;
    }
    
    sort(a.begin(), a.end());
    for(int i=0;i+1<n;i++){
        if(a[i] == a[i+1]){
            cout << 0 << endl;
            return 0;
        }
    }
    sort(b.begin(), b.end());
    for(int i=0;i+1<m;i++){
        if(b[i] == b[i+1]){
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;

    for(ll x=n*m;x>0;x--){
        if(isa[x] && isb[x]){
            ans *= 1;
        }else if(isa[x]){
            // count j (b[j] >= x)
            ll cnt = b.end() - lower_bound(b.begin(), b.end(), x);
            ans *= cnt;
            ans %= MOD;
        }else if(isb[x]){
            ll cnt = a.end() - lower_bound(a.begin(), a.end(), x);
            ans *= cnt;
            ans %= MOD;
        }else{
            ll cnta = a.end() - lower_bound(a.begin(), a.end(), x);
            ll cntb = b.end() - lower_bound(b.begin(), b.end(), x);
            ll rem = cnta * cntb - (n * m - x);
            ans *= rem;
            ans %= MOD;
        }
        // cout << x << " " << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm> // sort(ALL())
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue> // push(), front(), pop() 先入れ先出し
#include<map> // 連想配列 map<string, int>
#include<iomanip>
#include<set>
#include<utility>
using namespace std;
#define FOR(i, a, b) for(int i=(a); i<(b);  i++)
#define REP(i, n)    for(int i=0;   i<(n);  i++)
#define REP1(i, n)   for(int i=1;   i<=(n); i++)
#define pb push_back
#define mp make_pair
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define EPS 1e-7
#define ALL(obj) (obj).begin(), (obj).end()
using ul    = unsigned long;
using ll    = long long;
using ld    = long double;
using vint  = vector<int>;
using vll   = vector<ll>;
using pint  = pair<int, int>;
using pll   = pair<ll, ll>;
using vpint = vector<pint>;
using vpll  = vector<pll>;
const int INF = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
#define INT(argu) (int)(argu+EPS)



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

  int n;
  scan(n);
  vint a(n);
  REP(i, n) scan(a[i]);
  sort(ALL(a));
  REP(i, n-1){
    if(a[i]==a[i+1]){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  return 0;
}


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

int main(){
  int n;
  cin >> n;
  int p[n];
  int num = 0;
  for(int i = 0;i < n;i++){
    cin >> p[i];
    if(p[i] ==  i+1){
      num++;
    }
  }
  if(num == n || num == n-2){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n, k;
	int a[100];
	int a_1[100][100];
	int d[100];

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

	for (int i=0; i <= k - 1; i++) {
		cin >> d[i];
		for (int j = 0; j <= d[i]-1; j++) {
			cin >> a_1[i][j];
			a[a_1[i][j]] = 0;
		}
	}

	int p = 0;

	for (int i = 0; i <= n; i++) {
		if (a[i] != 0)
			p = p + 1;
	}
	cout << p;
}

Measured memory_bytes: 3196
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int N, M, C;
  cin >> N >> M >> C;
  vector <int> B(M);
  for (int i = 0; i < M; i++) {
	  cin >> B[i];
	}
  vector <vector <int> > A(N, vector <int>(M, 0));
  for (int i = 0; i < N; i++) {
	  for (int j = 0; j < M; j++) {
		  cin >> A[i][j];
		}
	}
  int ans = 0;
  for (int i = 0; i < N; i++) {
	  int score = C;
	  for (int j = 0; j < M; j++) {
		  score += A[i][j] * B[j];
		}
	  if (score > 0) {
		  ans++;
		}
	}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <string>

#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(int x=from;x<to;x++)

using namespace std;

int m10pow(int n){
int	res = 1;
	rep(i,n) res *= 10;
	return res;
}

int main(void){

string wk;
int n,su[8];
	cin >> n;
	rep(z,n){
		cin >> wk;
		rep(i,8) su[i]= wk[i] - '0';
		sort(su,su+8);
		int wkmin=0, wkmax=0;
		rep(i,8) wkmax += su[i] * m10pow(i);
		rep(i,8) wkmin += su[7-i] * m10pow(i);
//		printf("%d-%d\n",wkmax,wkmin);
		cout << wkmax - wkmin << endl; 
	}
	return 0;
	
	
}

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

int main(){
  int n;
  long long t;
  cin>>n>>t;

  long long a,b,ans=0;
  cin>>a;
  for(int i=1; i<n; i++){
    cin>>b;
    ans+=min(b-a, t);
    a=b;
  }
  ans+=t;
  cout<<ans<<endl;
}

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

using namespace std;

#define ll long long
#define mod 1000000007
#define lim 2010

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll dp[lim][lim];
	ll s[lim], t[lim];
	ll n, m;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		cin>>s[i];
	}
	for(int i=1; i<=m; i++){
		cin>>t[i];
	}
	memset(dp, 0, sizeof(dp));
	dp[0][0]=1;
	for (int i=0;i<=n;i++) dp[i][0]=1;
	for (int j=0;j<=m;j++) dp[0][j]=1; 

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			dp[i][j]=dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
			if(s[i] == t[j]){
				dp[i][j] += (dp[i-1][j-1])%mod;
			}
          	dp[i][j] =  (dp[i][j]+mod)%mod;
		}
	}
	cout<<dp[n][m];
}

Measured memory_bytes: 31872
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main(){
        int N,T;
        int c,t;
        int ans = 1001;
        scanf("%d %d",&N,&T);
        for(int i=0; i<N; i++){
           scanf("%d %d",&c,&t);
           if(t<=T && ans>c) ans=c;
        }
        if(ans==1001) printf("TLE\n");
        else printf("%d\n",ans);
        return 0;
}


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

using namespace std;

int * h;
int * dp;
bool * v;
int solve(int n, const int& max, const int& k){
	if (n == max -1)
		return 0;
	
	if (n == max){
		return	1e9;
	}
	
	if (v[n]) return dp[n];

	int * jp = new int[k];
	int mn = 1e9;
	for(int i = 1;i <=k;++i){
		if (n + i > max)
			break;
		jp[i-1] = solve(n+i, max, k) + abs(h[n] - h[n+i]);
		if (jp[i-1] < mn)
			mn = jp[i-1];
	}

	int cost = dp[n] = mn;
	v[n] = 1;

	return cost;
}

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

	h = new int[N];	
	dp = new int[N];
	v = new bool[N];

	fill(dp, dp + N, 0);
	fill(v, v + N, 0);

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


	cout << solve(0, N, k) << endl;
	return 0;
}


Measured memory_bytes: 54412
s = input()
k = int(input())
li = []
l = 0
r = min(len(s), 5)

while l != r:
    s1 = s[l:r]
    for i in range(1,len(s1)+1):
        s2 = s1[:i]
        li.append(s2)

    if r < len(s):
        r += 1
    l += 1

li = list(set(li))
li.sort()

print(li[k-1])


Measured memory_bytes: 5068
N,K=[int(x) for x in input().split()]
S=list(input())


if S[K-1]=='A':
    S[K-1]='a'
elif S[K-1]=='B':
    S[K-1]='b'
else :
    S[K-1]='c'
ans="".join(S)
print(ans)

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().compute();
    }

    void compute() {
        int N = scanner.nextInt();
        String S1 = scanner.next();
        String S2 = scanner.next();

        List<Boolean> dirs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            if (S1.charAt(i) == S2.charAt(i)) {
                dirs.add(true);
            } else {
                dirs.add(false);
                i++;
            }
        }
        int ans;
        if (dirs.get(0)) {
            ans = 3;
        } else {
            ans = 6;
        }
        for (int i = 1; i < dirs.size(); i++) {
            if (dirs.get(i - 1)) {
                ans = (int) ((long) ans * 2 % 1000000007);
            } else if (!dirs.get(i)) {
                ans = (int) ((long) ans * 3 % 1000000007);
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 23764
#include<stdio.h>
#include<string.h>
int main(){
    char S[5];
    scanf("%s",&S);
    int i=0;
    for(;S[i]!='\0';i++)
    {
        if (S[i]=='A' && S[i+1]=='C')
        {
             printf("Yes");
             return 0;
        }
    }
    printf("No");
    return 0;
}

Measured memory_bytes: 128
#![allow(non_snake_case)]
#![allow(unused_imports)]
 
use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;

#[fastout]
fn main() {
    input!{
        N: usize,
        M: usize,
        regular_service: [[usize; 2]; M],
    }
    let mut set_1: HashSet<usize> = HashSet::new();
    let mut set_N: HashSet<usize> = HashSet::new();
    
    for s in regular_service.iter() {
        // dbg!(&s);
        if s[0] == 1 {set_1.insert(s[1]);}
        if s[1] == N {set_N.insert(s[0]);}
    }

    let mut ans: &str = "IMPOSSIBLE";

    for i in set_1.iter() {
        if set_N.contains(i) {
            ans = "POSSIBLE";
            break;
        }
    }
    // dbg!(regular_service);
    // dbg!(set_1, set_N);
    println!("{}", ans);
}


Measured memory_bytes: 18080
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [0] * (n+2)
Q[0] = 1
t = 0
r = 1

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    global r
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q[r] = i
            r += 1
            #print(Q)

while t != r:
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Measured memory_bytes: 159056
#include <cstdio>
#include <vector>
#include <stack>

typedef struct Node {
    int id;
    int parent;
    int c[2];
    Node(){ id = 0; parent = -1; c[0] = -1; c[1] = -1;};
    Node(int i){ id = i; parent = -1; c[0] = -1; c[1] = -1;};
    ~Node(){};
} Node;

void postorder_iter(std::vector<Node> &nodes, int id){
    if(id == -1) return;
    postorder_iter(nodes, nodes[id].c[0]);
    postorder_iter(nodes, nodes[id].c[1]);
    std::printf("%d", id+1);
    if(nodes[id].parent == -1) std::printf("\n");
    else std::printf(" ");
}

int main(){
    int n;
    std::scanf("%d", &n);
    std::vector<int> preorder;
    std::vector<int> inorder;

    for(int i = 0; i < n; ++i){
        int v;
        std::scanf("%d", &v);
        --v;//adjust value                                                                                                                                                                                                          
        preorder.push_back(v);
    }
    for(int i = 0; i < n; ++i){
        int v;
        std::scanf("%d", &v);
        --v;//adjust value                                                                                                                                                                                                          
        inorder.push_back(v);
    }

    std::vector<Node> nodes;
    for(int i = 0; i < n; ++i){
        Node node(i);
        nodes.push_back(node);
    }
    std::vector<bool> isExist(n, 0);
    int i = 0;
    int j = 0;
    int p = -1;
    while(i < n && j < n){
        while(preorder[i] != inorder[j]){
            nodes[preorder[i]].c[0] = preorder[i+1];
            nodes[preorder[i]].parent = p;
            isExist[preorder[i]] = true;
            p = preorder[i];
            ++i;
        }
        nodes[preorder[i]].parent = p;
	isExist[preorder[i]] = true;
        ++i;
        if(i == n) break;
        while(isExist[inorder[j]]) ++j;
        p = inorder[j - 1];
        nodes[p].c[1] = preorder[i];

    }

    postorder_iter(nodes, preorder[0]);
    return 0;
}



Measured memory_bytes: 2796
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

long gcd( long b, long a )
{
    // suppose b <= a

    long r = 0;
    while( (r = a % b) != 0 ) {
        a = b;
        b = r;
    }
    return b;
}

int main(int argc, char* argv[])
{
    long n, x;
    scanf("%ld %ld", &n, &x);

    long xx[100000]={0};
    long i, j;
    for(i=0; i<n; i++) {
        scanf("%ld", &(xx[i]) );
        xx[i] = abs(xx[i] - x);
    }
    std::sort( xx + 0, xx + n );

    long ans = xx[0];
    for(i=1; i<n; i++) {
        ans = gcd( ans, xx[i] );
    }

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

    return 0;
}





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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    long n, x;
    cin >> n >> x;
    long res = n;
    long a = x;
    long b = n - x;
    if (a < b) swap(a, b);
    while (a != b) {
         long t = (a - 1) / b;
         res += b * 2 * t;
         a -= b * t;
         swap(a, b);
    }
    res += a;
    cout << res;

    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
V = list(map(int,input().split()))

Q = min(N,K)+1
res = 0
for a in range(Q):
    for b in range(Q-a):
        W = V[:a] + V[N-b:]
        W.sort()
        for k in range(min(K-a-b,len(W))):
            if W[k] < 0:
                W[k] = 0
            else:
                break
        res = max(res,sum(W))

print(res)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

#define MAX 55
#define MINF -(1e8)

int N,M,a[MAX],b[MAX],c[MAX];
int memo[MAX][MAX][MAX];

int solve(int n,int l1,int m){
    if(n == N) return 0;
    int &res = memo[n][l1][m];
    if(res != MINF) return res;
    for(int i = 0 ; i <= min(8,m) ; i++){
        for(int j = 0 ; j <= i ; j++){
            for(int k = 0 ; k <= min(l1,8-j) ; k++){
                int cost = (j+k == 0 ? c[n] : a[n]*j+b[n]*k);
                res = max(res,solve(n+1,i,m-i)+cost);    
            }
        }
    }
    return res;
}

int main(){
    cin >> N >> M;
    for(int i = 0 ; i < N ; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    fill(&memo[0][0][0],&memo[MAX-1][MAX-1][MAX-1],MINF);
    cout << solve(0,0,M) << endl;
    return 0;
}

Measured memory_bytes: 1812
import math

K = int(input())

ans = 0
for x in range(1, K + 1, 1):
    for y in range(1, K + 1, 1):
        ans = ans + sum(list(map(lambda z: math.gcd(math.gcd(x, y), z), range(1, K+1, 1))))

print(ans)

Measured memory_bytes: 9216
def fastio():
    import sys
    from io import StringIO 
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, k = I()
l = []
for i in range(n): 
    l.append(I()[0])
l.sort()
ans = MOD
# print(l)
for i in range(k, n + 1):
    ans = min(ans, l[i-1] - l[i-k])
print(ans)

Measured memory_bytes: 12044
// 177

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <iomanip>
#include <climits>
#include <string>
#include <cmath>

using namespace std;
using ll = long long int;
#define NUM 1000000007

int main(){
    ll a, b, c, d, buf = LLONG_MIN;
    cin >> a >> b >> c >> d;
    if(buf < a*c) buf = a*c;
    if(buf < a*d) buf = a*d;
    if(buf < b*c) buf = b*c;
    if(buf < b*d) buf = b*d;
    cout << buf << endl;
    return 0;
}

Measured memory_bytes: 3636
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>n;
    //vector<vector<ll>> v(tate,vector<ll> (yoko));
    vector<ll> v(n);
    rep(i,n)   cin >> v[i];
    sum=1;
    rep(i,n){
        if(v[i]==0){
            cout<<0<<endl;
            return 0;
        }
    }
    maxi=pow(10,18);
    ll lastsum;
    rep(i,n){
        sum*=v[i];
        if(sum>maxi||lastsum>sum){
            cout<<-1<<endl;
            return 0;
        }
        lastsum=sum;
    }
    cout<<sum<<endl;

    return 0;
}


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<bool> b(n, false);
    for (Int i = 0; i < n; i++) {
        b[i] = (a[i] == i + 1);
    }
    Int res = 0;
    for (Int i = 0; i < n - 1; i++) {
        if (b[i]) {
            res++;
            if (b[i + 1]) {
                b[i + 1] = false;
            }
        }
    }
    if (b.back()) res++;
    dump(res);
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=3000;
int p,a[N],f[N],invf[N],ans[N];
int C(int n,int m)
{
    if(m>n) return 0;
    return f[n]*invf[n-m]%p*invf[m]%p;
}
int main()
{
    scanf("%d",&p);
    f[0]=invf[0]=invf[1]=1;
    for(int i=1;i<p;i++) f[i]=f[i-1]*i%p;
    for(int i=2;i<p;i++) invf[i]=(p-p/i)*invf[p%i]%p;
    for(int i=2;i<p;i++) invf[i]=invf[i]*invf[i-1]%p;
    for(int i=0;i<=p-1;i++) scanf("%d",&a[i]);
    for(int i=0;i<=p-1;i++)
    {
        if(a[i])
        {
            int t=1;
            for(int j=p-1;j>=0;j--)
                ans[j]+=C(p-1,j)*t%p,t=t*(p-i)%p;
        }
        else ans[0]++;
    }
    for(int i=0;i<=p-1;i++)
        printf(i==p-1?"%d\n":"%d ",(p-ans[i]%p)%p);
}


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

int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(i%2==0&&s.at(i)!='R'&&s.at(i)!='U'&&s.at(i)!='D'){
      cout << "No" << endl;
      return 0;
    }
     if(i%2==1&&s.at(i)!='L'&&s.at(i)!='U'&&s.at(i)!='D'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


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

int main(){
  int N,S,T,H,W,x,y;// S->y T->x
  while(cin >> N && N){
    cin >> W >> H;
    int imap[H+140][W+140],graph[H+140][W+140];
    for(int i=0;i<=H+110;i++)for(int j=0;j<=W+110;j++)imap[i][j] =graph[i][j] = 0;
    for(int i=0;i<N;i++){
      cin >> x >> y;
      imap[y][x] = 1;
    }

    int plus;
    //Create DP-graph
    for(int i=1;i<=H+100;i++){
      plus = 0;
      for(int j=1;j<=W+100;j++){
	if(imap[i][j] == 1){
	  plus++;
	}
	graph[i][j] = plus+graph[i-1][j];

      }
    }

    int ans = 0;
    cin >> S >> T;
    for(int i=1;i<=H;i++){
      for(int j=1;j<=W;j++){
	ans = max(ans,graph[i+T-1][j+S-1]-graph[i+T-1][j-1]-graph[i-1][j+S-1]+graph[i-1][j-1]);
      }
    }
    cout << ans << endl;



  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> v(m);
    for (int i = 0; i < m; i++) {
        cin >> v[i];
    }
    
    int cnt = 0, sum, a;
    for (int i = 0; i < n; i++) {
        sum = c;
        for (int j = 0; j < m; j++) {
            cin >> a;
            sum += a * v[j];
        }
        if (sum > 0) {
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
import std.conv, std.functional, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }




void main() {
  try {
    for (; ; ) {
      const N = readInt();
      auto A = new long[N];
      auto B = new long[N];
      foreach (i; 0 .. N) {
        A[i] = readLong();
        B[i] = readLong();
      }
      
      auto ts = new Tuple!(long, int)[N];
      foreach (i; 0 .. N) {
        ts[i] = tuple(A[i] + B[i], i);
      }
      ts.sort().reverse();
      long ans;
      foreach (j; 0 .. N) {
        const i = ts[j][1];
        if (j % 2 == 0) {
          ans += A[i];
        } else {
          ans -= B[i];
        }
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 5244
#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int x,y,s;
    while(cin>>x>>y>>s,x){
        int ans=0;
        for(int i=1;i<=s-1;++i){
            for(int j=i;j<=s-1;++j){
                if(i*(100+x)/100+j*(100+x)/100==s)ans=max(ans,i*(100+y)/100+j*(100+y)/100);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

int main(){
    // ll x, y;
    // cin >> x >> y;

    // ll dev = y/x;
    // ll i = 0;
    // for(i;i<63;i++){
    //     if(dev<pow(2, i)){
    //         break;
    //     }
    // }
    // cout << i << endl;


    ll x, y;
	cin >> x >> y;
	ll sum = y / x;
	ll iwa = 1;
	ll ans = 0;
	while (iwa <= sum) {
		iwa *= 2;
		ans++;
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int main(){
    long long a[3]={};
    scanf("%lld%lld%lld",&a[0],&a[1],&a[2]);
    if(a[0]%2&&a[1]%2&&a[2]%2){
        std::sort(a,a+3);
        printf("%lld\n",a[0]*a[1]);
    }
    else puts("0");
}


Measured memory_bytes: 128
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

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;
}

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int N,M;
    cin >> N >> M;
    vector<string> a(N);
    vector<string> b(M);
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < M; i++) cin >> b[i];
    bool flag = true;
    for(int x = 0; x < N; x++){
        for(int y = 0; y < N; y++){
            if(x + M - 1 >= N || y + M - 1 >= N) continue;
            flag = true;
            for(int i = 0; i < M; i++){
                for(int j = 0; j < M; j++){
                    int xx = x + i;
                    int yy = y + j;
                    if(a[xx][yy] != b[i][j]) flag = false;
                }
            }
            if(flag) break;  
        }
        if(flag) break;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3636