akhauriyash/Code-Regression huggingface dataset:
object Main extends App {
  import scala.io.StdIn._

  val Array(a, b, k) = readLine.trim.split(' ').map(_.toInt)
  println((1 to gcd(a, b)).filter(i ⇒ a % i == 0 && b % i == 0).reverse(k - 1))
  def gcd(a: Int, b: Int): Int = {
    b match {
      case 0L ⇒ a
      case _ ⇒ gcd(b, a % b)
    }
  }
}


Measured memory_bytes: 27592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    vector<pair<ll, ll>> bc(m);
    rep(i, m) cin >> bc[i].first >> bc[i].second;
    sort(all(bc), [](const pair<ll, ll> &a, const pair<ll, ll> &b){ return a.second > b.second; });
    ll idx = 0;
    rep(i, n) {
        if (a[i] >= bc[idx].second) break;
        a[i] = bc[idx].second;
        bc[idx].first--;
        if (bc[idx].first == 0) {
            idx++;
            if (idx == m) break;
        }
    }
    ll ans = accumulate(all(a), 0LL);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    friend std::istream &operator>>(std::istream &in, mint &o) {
        ll a;
        in >> a;
        o = a;
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const mint &o) {
        out << o.x;
        return out;
    }

};


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

    vector<ll> as(n);
    rep(i, n) cin >> as[i];

    auto ft = [&](int i) -> mint {
        mint ans = 0;
        rep(j, i) {
            if (as[j] > as[i]) ans = ans + 1;
        }
        return ans;
    };

    mint ans = 0;
    rep(i, n) {
        mint t = ft(i);
        mint now = t * k;
        ans += now;
    }

    auto fm = [&](int i) -> mint {
        mint ans = 0;
        rep(j, n) {
            if (as[j] < as[i]) ans = ans + 1;
        }
        return ans;
    };

    rep(i, n) {
        mint m = fm(i);
        mint now = m  * k * (k - 1) / 2;
        ans += now;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N, count = 0;
  cin >> N;
  
  for ( int i = 0; i < N; i++) {
    int A, cnt = 0;
    cin >> A;
    
    if ( A % 2 != 0 ){
      count = 0;
      break;
    }
    
    while ( A > 1 ){
      
      if ( A % 2 == 0 ){
        A /= 2;
        cnt++;
      }else
        break;
      
      if ( cnt == count )
        break;
      
    }
    
      count = cnt;
    
  }

  cout << count << endl;
  
}

Measured memory_bytes: 256
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
vector<int> ar;
int n, k;
int judge(int border) {
	if (ar[border] >= k) return 0;
	int gogo[6000] = {};
	gogo[0] = 1;
	for (int i = 0;i < n;++i) {
		if (i != border) {
			for (int q = k - 1;q >= 0;--q) {
				if (q + ar[i] < k) {
					gogo[q + ar[i]] |= gogo[q];
				}
			}
		}
	}
	for (int i = k - ar[border];i < k;++i) {
		if (gogo[i]) return 0;
	}
	return 1;
}
int main() {
	cin >> n >> k;
	REP(i, n) {
		int tmp;
		cin >> tmp;
		ar.push_back(tmp);
	}
	sort(ar.begin(), ar.end());
	int bot = 0;
	int top = n - 1;
	while (top - bot > 1) {
		int mid = (top + bot) / 2;
		if (judge(mid)) {
			bot = mid;
		}
		else top = mid;
	}
	if (judge(top)) {
		cout << top+1 << endl;
		return 0;
	}
	else if (judge(bot)) {
		cout << bot+1 << endl;
	}
	else cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 384
def main():
  M,D=map(int,input().split())

  ans=0
  for i in range(22,D+1):
    if min(divmod(i,10)) in (0,1):
      continue
    q,r=divmod(i,10)
    if q*r <= M:
      ans += 1

  print(ans)
  
if __name__=="__main__":
  main()

Measured memory_bytes: 9168
N_M = list(map(int ,input().split( )))
Xs = list(map(int ,input().split( )))
Xs.sort()

difference = []
for i in range(len(Xs)-1):
    difference.append(Xs[i+1] - Xs[i])
    
difference.sort()
sum_d = 0
for i in range(N_M[1] - N_M[0]):
    sum_d += difference[i]

print(sum_d)

Measured memory_bytes: 13968
n = int(input())
a_array = [int(x) for x in input().split()]
b_array = [int(x) for x in input().split()]
c_array = [int(x) for x in input().split()]

res = b_array[a_array[0] - 1]
now_a = a_array[0]
for i in range(1, n):
    res += b_array[a_array[i] - 1]
    if now_a + 1 == a_array[i]:
        res += c_array[a_array[i - 1]-1]
    now_a = a_array[i]
print(res)


Measured memory_bytes: 3064
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        mut ab: [(i64, i64); n],
    }

    ab.sort_by_key(|&(a, b)| a + b);
    ab.reverse();

    let mut ans = 0;

    for i in 0..n {
        if i % 2 == 0 {
            ans += ab[i].0;
        } else {
            ans -= ab[i].1;
        }
    }

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


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


int main(){
  string S; cin>>S;
  int ans=INF;
  rep(i,S.length()-2){
    int a[3];
    int X=0;
    rep(j,3){
      a[j]=S[i+j]-'0';
      X+=pow(10,2-j)*a[j];
    }
    ans=min(ans,abs(X-753));
  }
  cout<<ans<<endl;
  return 0;
}
    


Measured memory_bytes: 3844
import sys
# import math
# import decimal
# import queue
# import bisect
# import heapq
import time
# import itertools

mod = int(1e9+7)
INF = 1<<29

def main():
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        if a[i] % 2 == 0:
            if a[i] % 3 != 0 and a[i] % 5 != 0:
                print("DENIED")
                return
    print("APPROVED")
    return

if __name__=='__main__':
    main()

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

using namespace std;

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

    string s;
    cin >> s;
    int cnt = 0;

    for (int i = 1; i < int(s.size()); i++) {
        if (s[i] != s[i - 1]) {
            cnt++;
        }
    }
    cout << cnt << '\n';

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
 
int main()
{
  while(1){
    int h,w;
    cin >> h >> w;
    if(h == 0 && w == 0) break;
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        cout << "#";
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))
if __name__ == "__main__":
    k = I()
    s = S()
    str =  s[:k] + "..."
    print(s if len(s) <= k else str)

Measured memory_bytes: 9220
n, k = map(int, input().split())
hs = []
for i in range(n):
    hs.append(int(input()))

hs.sort()
mini = 10 ** 10
for i in range(n-k+1):
    sample = abs(hs[i] - hs[i+k-1])
    if mini > sample:
        mini = sample

print(mini)

Measured memory_bytes: 7384
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,M,N;
int main()
{
	cin>>n>>m;
	n--;
		if((m%4)==1)M=1;
		else if((m%4)==3) M=0;
		else if((m%4)==2) M=m+1;
		else if((m%4)==0) M=m;
	if(n==-1)
	{
		N=0;
	}
	else 
	{
		if((n%4)==1)N=1;
		else if((n%4)==3) N=0;
		else if((n%4)==2) N=n+1;
		else if((n%4)==0) N=n;
	}
	cout<<(N^M)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
using namespace std;
template<class T>inline void rd(T &x) {
  x=0; int ch=getchar(),f=0;
  while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
  while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  if(f)x=-x;
}
const int inf=0x3f3f3f3f;
int n,m;
int main()
{
  cin>>n>>m;
  cout<<n*(n-1)/2+m*(m-1)/2<<endl;
  return 0;
}

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

#define F first 
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 1010;

int n, m;
PII a[N];

bool cmp(PII a, PII b)
{
	if (a.S != b.S) return a.S < b.S;
	else return a.F > b.F;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i ++ )
	{
		int l, r;
		scanf("%d%d", &l, &r);
		l ++ ;
		a[i] = {l, r};
	}
	sort(a, a + m, cmp);
	
	int res = 0, pos = -0x3f3f3f3f;
	for (int i = 0; i < m; i ++ )
		if (a[i].F > pos)
		{
			pos = a[i].S;
			res ++ ;
		}
	
	printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 4600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
namespace IO
{
	template <typename T> inline void read(T &x)
	{
		int f = 1; x = 0; char c = getchar();
		for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
		for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
		x *= f;
	}

	template <typename T> inline void chkmax(T &x, T y) { x = x > y ? x : y; }
	template <typename T> inline void chkmin(T &x, T y) { x = x < y ? x : y; }

	template <typename T> inline void write(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
	template <typename T> inline void writesp(T x) { write(x); putchar(' '); }
	template <typename T> inline void writeln(T x) { write(x); putchar('\n'); }
}
using namespace IO;
int main(){
	int n;
	read(n);
	if (n % 1000 == 0) puts("0");
	else writeln(1000 - n % 1000);
  return 0;
}

Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"sync"
)


func main() {
	n := scanSplitedInt()
	array := make([]uint64, 0, n)

	// 配列を作る
	for i := 0; i < n; i++ {
		array = append(array, scanSplitedUint64())
	}

	// 累積和を作る
	cusum := make([]uint64, n+1)
	for i := 0; i < n; i++ {
		cusum[i+1] = (cusum[i] + array[i])
	}

	var ans uint64
	for i, v := range array {
		sum := (cusum[n] - cusum[i+1]) % 1000000007
		ans += v * sum
		ans %= 1000000007
	}

	fmt.Println(ans)
}


var once sync.Once
var scanner *bufio.Scanner

func scan() {
	once.Do(func() {
		scanner = bufio.NewScanner(os.Stdin)
		scanner.Split(bufio.ScanWords)
	})
	scanner.Scan()
}

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

func scanSplitedUint64() uint64 {
	scan()
	val, err := strconv.ParseUint(scanner.Text(), 10, 64)
	check(err)
	return val
}

func scanSplitedInt() int {
	scan()
	val, err := strconv.Atoi(scanner.Text())
	check(err)
	return val
}


Measured memory_bytes: 7532
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TEST freopen("in.txt","r",stdin);
#define ab(a) ((a < 0) ? (-(a)) : (a))
#define all(a) a.begin(), a.end()
#define ones(a) __builtin_popcount(a)

int main(){
  fastIO;
  int n;
  cin >> n;
  string s;
  cin >> s;
  int c1 = 0, c2 = 0;
  for(int i = 1;i < n;i ++ )
    c2 += (s[i] == 'E');
  int ans = (int)1e9 + 9;
  for(int i = 0;i < n;i ++ ){
    ans = min(ans, c1 + c2);
    c1 += (s[i] == 'W');
    if(i < n-1)
      c1 -= (s[i + 1] == 'E');
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef pair<int, int> p;
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; }
int Inf = (1<<30);
ll inf = (1LL<<60);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'e' && s[i + 3] == 'r' && s[i + 4] == 'd') {
			i += 4;
		}
		else if (s[i] == 'r' && s[i + 1] == 'e' && s[i + 2] == 'm' && s[i + 3] == 'a' && s[i + 4] == 'e' && s[i + 5] == 'r' && s[i + 6] == 'd') {
			i += 6;
		}
		else if (s[i] == 'e' && s[i + 1] == 's' && s[i + 2] == 'a' && s[i + 3] == 'r' && s[i + 4] == 'e') {
			i += 4;
		}
		else if (s[i] == 'r' && s[i + 1] == 'e' && s[i + 2] == 's' && s[i + 3] == 'a' && s[i + 4] == 'r' && s[i + 5] == 'e') {
			i += 5;
		}
		else {
			cout << "NO";
			return(0);
		}
	}
	cout << "YES";
	return(0);
}

Measured memory_bytes: 512
import numpy as np
import itertools

N, M, X = map(int, input().split())

price = []
algo = []

for i in range(N):
  l = list(map(int, input().split()))
  price_var = l[0]
  price.append(price_var)
  l.pop(0)
  algo.append(l)

A = []
B = []
for i in range(N):
  L = list(itertools.combinations(price,i+1))
  L2 = list(itertools.combinations(algo,i+1))
  for j in range(len(L)):
    A.append(sum(L[j]))
    B.append(L2[j])

d = zip(A, B)
d = sorted(d)
ans = []
for i in range(len(d)):
  R = [0]*M
  R = np.array(R)
  for j in range(len(d[i][1])):
    R = R + np.array(d[i][1][j])
    if min(R) >= X:
      ans.append(d[i][0])

if len(ans) >= 1:
  print(min(ans))
else:
  print(-1)

Measured memory_bytes: 28188
#include <iostream>
#include <algorithm>

using namespace std;

int des[10];
int g[210][210];

const int INF = 1e9;

int main()
{
    int n, m, r;
    cin >>n>>m>>r;
    
    for(int i=0;i<r;i++){
        cin >>des[i];
    }
    sort(des, des+r);
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            g[i][j] = INF;
        }
    }
    for(int i=0;i<m;i++){
        int u, v, c;
        cin>> u>>v>>c;
        g[u][v] = g[v][u] = c;
    }
 
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
            }
        }
    }
    
    int ans = INF;
    do{
        int sum = 0;
        for(int i=0;i<r-1;i++){
            sum += g[des[i]][des[i+1]];
        }
        ans = min(ans, sum);
    }while(next_permutation(des, des+r));
    
    cout << ans<<endl;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
int A[404040],B[404040];
ll C[404040];
vector<pair<int,int>> E[4040];
int Q;
ll D[4040][4040];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void dfs(int st,int cur,int pre,int ma) {
	D[st][cur]=ma;
	FORR(e,E[cur]) if(e.first != pre) {
		dfs(st,e.first,cur,max(ma,e.second));
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	priority_queue<pair<int,int>> EE;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i], A[i]--, B[i]--;
		EE.push({-C[i],i});
	}
	
	ll tot=0;
	while(EE.size()) {
		auto e=EE.top();
		x = A[e.second];
		y = B[e.second];
		EE.pop();
		if(uf[x]!=uf[y]) {
			uf(x,y);
			E[x].push_back({y,-e.first});
			E[y].push_back({x,-e.first});
			tot+=-e.first;
		}
	}
	
	FOR(i,N) dfs(i,i,-1,0);
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		cout<<tot-D[x-1][y-1]<<endl;
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 141292
def honest_or_unkind(n, tests):
    max_honest = 0
    for i in range(pow(2, n)):
        i = format(i, 'b').zfill(n)
        if str(i).count('1') > max_honest:
            flag = True
            for j, v in enumerate(str(i)):
                if v == '1':
                    for t in tests[j]:
                        if str(i)[t[0]-1] != str(t[1]):
                            flag = False
            if flag:
                max_honest = str(i).count('1')
    print(max_honest)

tests = []
n = int(input())
for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
        tmp.append([int(k) for k in input().split()])
    tests.append(tmp)

honest_or_unkind(n, tests)

Measured memory_bytes: 44764
// SeeAlso: https://atcoder.jp/contests/abc131/tasks/abc131_c

#include <bits/stdc++.h>

using namespace std;

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

#define MAX 100000

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

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

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

inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

ll a,b,c,d;

ll cnt(ll a,ll b,ll c){return b/c-a/c;}

int main() {
    
    cin >> a >> b >> c >> d;
    a--;
    ll e = lcm(c, d);
    ll x = cnt(a,b,c);
    ll y = cnt(a,b,d);
    ll z = cnt(a,b,e);

    cout << (b-a-x-y+z) << endl;

    return 0;
}



Measured memory_bytes: 256
from sys import stdin


[K, S] = list(map(int, stdin.readline().rstrip().split()))

count=0

for x in range(K+1):
    for y in range(K+1):
        if x + y > S:
            continue
        if S - (x + y) <= K:
            #print("%d %d %d" % (x, y, S-(x+y)))
            count = count + 1

print(count)



Measured memory_bytes: 2940
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,x,n) for (int i = x;i < n;++i)

int c[2000];

int main() {
	int n, x;
	scanf("%d%d", &n, &x);
	f(i, 0, n)scanf("%d", c + i);
	ll an = 1e18;
	f(i, 0, n) {
		ll r = (ll)i*x;
		deque<int> d;
		f(j, 0, i) {
			while (!d.empty() && c[j] < c[d.back()])d.pop_back();
			d.push_back(j);
		}
		f(j, 0, n) {
			int z = j + i;
			if (z >= n)z -= n;
			while (!d.empty() && c[z] < c[d.back() >= n ? d.back() - n : d.back()])d.pop_back();
			d.push_back(j + i);
			while (d.front() < j)d.pop_front();
			r += c[d.front() >= n ? d.front() - n : d.front()];
		}
		an = min(an, r);
	}
	printf("%lld", an);
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
    int S,h,m,s;
    cin>>S;
    h=S/3600;
    m=(S-3600*h)/60;
    s=(S-h*3600)%60;
    cout<<h<<":"<<m<<":"<<s<<endl;
    return 0;
}


Measured memory_bytes: 3104
def main():
    N = int(input())
    T, X, Y = 0, 0, 0
    for _ in range(N):
        t, x, y = list(map(int, input().split()))
        dx = abs(x - X)
        dy = abs(y - Y)
        dt = t - T
        if (dx + dy) % 2 != dt % 2:
            print('No')
            return
        if dx + dy > dt:
            print('No')
            return
        T, X, Y = t, x, y
    print('Yes')

main()


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

string a;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  getline(cin,a);
  int n = a.size();
  if (a[n-1] != 's')
  {
    cout << a << 's';
  }
  else
  {
    for(int i=0; i<=n-1; i++) cout << a[i];
      cout << "es";
  }
  return 0;
}


Measured memory_bytes: 3648
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {

	sc := bufio.NewScanner(os.Stdin)
	count := 0
	sc.Scan()
	in := sc.Text()
	a := strings.Split(in, " ")

	val1, _ := strconv.Atoi(a[0])
	val2, _ := strconv.Atoi(a[1])
	val3, _ := strconv.Atoi(a[2])

	for i := val1; i <= val2; i++ {
		if val3%i == 0 {
			count++
		}
	}

	fmt.Println(count)

}



Measured memory_bytes: 1096
import std.stdio, std.string, std.array, std.conv;

void main() {
    int n = readln.chomp.to!int;
    int[] a = readln.chomp.split.to!(int[]);
    int q = readln.chomp.to!int;
    int[] m = readln.chomp.split.to!(int[]);
    bool[] check = new bool[2001];
    foreach (i; 0 .. 1<<n) {
        int sum = 0;
        foreach (j; 0 .. n) {
            if (i & 1<<j) sum += a[j];
        }
        check[sum] = true;
    }
    foreach (x; m) {
        writeln(check[x] ? "yes" : "no");
    }
}


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

int main(){
	int a,p,s=0;
	
	cin>>a;
	
	p=a;
	
	while(p!=0){
		s+=p%10;
		p=p/10;
	}
	
	if(a%s==0){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
		
	}
	return 0;
}

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

using namespace std;

int main()
{
	int n, x;
	cin >> n >> x;
	vector<int> v(n + 1);
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		v[i] += v[i - 1];
		if (v[i] <= x) {
			ans++;
		}
		else {
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define watch(x) cout<<(#x)<<" is "<<(x)<<endl;
#define mod 1000000007
#define pb push_back
#define endl '\n'

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

	int a[10][10]={0};

	for(int i=1;i<=n;i++)
	{
		string s = to_string(i);
		int last = s[s.size()-1] - '0';
		int first = s[0] - '0';
		a[first][last]++;

	}
	int ans =0;
	for(int i=0;i<=9;i++)
	{
		for(int j=0;j<=9;j++)
		{
			ans+=a[i][j]*a[j][i];
		}
	}
	cout<<ans<<endl;


}

Measured memory_bytes: 256
h,w,k = map(int, input().split())
grid = [input() for _ in range(h)]

ans = 0

for i in range(2**h):
    for j in range(2**w):
        count = 0
        for m in range(h):
            for l in range(w):
                if (i>>m)&1==0 and (j>>l)&1==0 and grid[m][l] == "#":
                    count+=1
        if count == k: ans+=1
print(ans)

Measured memory_bytes: 9148
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int arr[300005];
int num[300005];
int total;
inline bool test(int i,int j){ /// if K==i is j possible?
    int usable=0;
    total-=num[j+1];
    num[j]+=num[j+1];
    num[j+1]=0;
    return total>=i*j;
}
int main(){
    scanf("%d",&n);
    int t;
    for (int x=0;x<n;x++){
        scanf("%d",&t);
        arr[t]++;
    }
    for (int x=1;x<=n;x++){
        num[arr[x]]++;
    }
    total=n;
    int curr=n;
    for (int x=1;x<=n;x++){
        while (!test(x,curr)) curr--;
        printf("%d\n",curr);
    }
}


Measured memory_bytes: 3072
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintStream out = new PrintStream(System.out);
        int r, g, b;

        r = sc.nextInt();
        g = sc.nextInt();
        b = sc.nextInt();

        if ((g*10+b)%4 == 0) {
            out.println("YES");
        } else {
            out.println("NO");
        }
        
        
        sc.close();
    }
}

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

const long long inf = 1e17;

const int maxn = 1e5+10;

long long f[maxn << 2];

long long res[maxn];

typedef pair<int,int> II;
typedef pair<II, int> III;

III a[maxn];

void update(int k, int l, int r,int x, long long v) {
	if (l > x || r < x) return;
	if (l == r) {
		f[k] = min(f[k], v);
	} else {
		int g = (l + r) >> 1;
		update(k << 1, l , g, x, v);
		update(k << 1 | 1, g + 1, r, x , v);
		f[k] = min(f[k << 1], f[k << 1 | 1]);
	}
}

long long get(int k, int l,int r,int u,int v) {
	if (l > v || r < u) return inf;
	if (l >= u && r <= v) {
		return f[k];
	} else {
		int g = (l+r) >> 1;
		return min(get(k << 1, l, g, u, v), get(k << 1 | 1, g + 1, r, u, v));
	}
}

int main() {
	//freopen("inp.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n = 0;
	int m = 0;
	cin >> m >> n;
	for(int i=0;i<n;i++) {
		cin >> a[i].first.first >> a[i].first.second >> a[i].second;
	}
	
	fill(f, f + (maxn << 2), inf);
//	cerr << f[0] <<" " << f[1] << endl;
	
	sort(a, a+n);
	
	update(1, 1, m, 1, 0);
	long long ans = inf;
	for(int i=0;i<n;i++) {
		int l = a[i].first.first;
		int r = a[i].first.second;
		int c = a[i].second;
		long long t = get(1, 1, m, l, r);
		res[i] = min(inf, t + c); 
		update(1, 1, m, r, res[i]);
		if (r == m) {
			ans = min(ans, res[i]);
		}
	}
	
	if (ans == inf) cout << -1;
	else cout << ans;

	return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=2e9;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a<=c&&c<=b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int L = Integer.parseInt(sc.next());
        int R = Integer.parseInt(sc.next());

        sc.close();
        
        //R-Lが2019"以上"の場合は2019の倍数が含まれる
        if (R - L >= 2019) {

            System.out.println(0);
            System.exit(0);
        }

        long mod2019;
        //は2019で割ったあまりだから最大でも2018
        long min = 2018;

        for (long i = L; i < R; i++) {

            for (long j = i+1; j <= R; j++) {

                mod2019 = (i*j)%2019;

                if (min > mod2019) {

                    min = mod2019;
                }
                
                //2019は素数だから以下の記述は無意味、バグの発生原因になる
//                if (min == 0) {
//
//                    break;
//                }
            }

//            if (min == 0) {
//
//                break;
//            }
        }

        System.out.println(min);
    }

}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  int l, n;
  cin>>l>>n;
  vecll x(n);
  REP(i,n)cin>>x[i];
  vecll psum(n+2);
  partial_sum(ALL(x), begin(psum)+1);
  psum.back() = psum[n] + l;
  vecll fwd0(n+2, 0);
  vecll fwd1(n+2, 0);
  FOR(i,1,n) {
    ll start0 = 0;
    ll start1 = 0;
    ll rnum = n-1-i;
    if (i > rnum) {
      start0 = i - rnum;
      start1 = i - rnum - 1;
    }
    fwd0[i] = (psum[i] - psum[start0]) * 2;
    fwd1[i] = (psum[i] - psum[start1]) * 2;
  }
  vecll bwd0(n+2, 0);
  vecll bwd1(n+2, 0);
  REP(ri,n-1) {
    ll i = n-ri;
    ll num = ri+1;
    ll start0 = n+1;
    ll start1 = n+1;
    ll rnum = n-1-num;
    if (num > rnum) {
      start0 = i-1 + rnum;
      start1 = i-1 + rnum + 1;
    }
    bwd0[i] = (l * (start0 + 1 - i) - (psum[start0] - psum[i-1])) * 2;
    bwd1[i] = (l * (start1 + 1 - i) - (psum[start1] - psum[i-1])) * 2;
  }
  ll mx = 0;
  FOR(i,0,n) {
    int fi = i-1;
    int fnum = fi+1;
    int bi = i+1;
    int bnum = n-bi;
    mx = max(mx, fwd0[fi+1] + x[i] + bwd0[bi+1]);
    mx = max(mx, fwd0[fi+1] + (l - x[i]) + bwd0[bi+1]);
    if (fnum > bnum) {
      mx = max(mx, fwd1[fi+1] + (l - x[i]) + bwd0[bi+1]);
    }
    if (fnum < bnum) {
      mx = max(mx, fwd0[fi+1] + x[i] + bwd1[bi+1]);
    }
  }
  cout << mx << endl;
  return 0;
}


Measured memory_bytes: 9600
a=int(input())                      
b=list(map(int, input().split()))   
c=0                                 
for i in range(a):                  
    if i+1 != b[i]:                 
        c+=1                        
if c <= 2:                          
    print("YES")                    
else:                               
    print("NO")                     
                       

Measured memory_bytes: 3060
import math
N = int(input())
P_list = [int(i) for i in input().split()]
Q_list = [int(i) for i in input().split()]
def dic_num(N, X_list):
    now_num = N
    ans = 0
    while len(X_list)>1:
        value = (X_list[0]-1)*math.factorial(now_num-1)
        ans += value
        now_num -= 1
        for i,n in enumerate(X_list):
            if n > X_list[0]:
                X_list[i]=X_list[i]-1
        X_list.pop(0)
    return ans
print(abs(dic_num(N, P_list)-dic_num(N, Q_list)))

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

using namespace std;

string a = "dream";
string b = "erase";
const int size = 5;

bool isSame(char c[], string s){
  for(int i = 0; i < s.length(); i++){
    if(s[i] != c[i])
      return false;
  }
  return true;
}

bool isFormable(char c[]){
  if(c[0] == '\0'){
    return true;
  }
  if(isSame(c, b)){
    if(c[size] == 'r'){
      return isFormable(c + size + 1);
    } else {
      return isFormable(c + size);
    }
  } else if(isSame(c, a)){
    if(isFormable(c + size)){
      return true;
    } else {
      return c[size] == 'e' && c[size+1] == 'r' &&
              isFormable(c + size + 2);
    }
  }
  return false;

}

int main() {
  char buff[100001];
  scanf("%s", buff);

  bool result = isFormable(buff);



  cout << (result ? "YES" : "NO") << endl;

  return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <functional>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <climits>
#include <unordered_map>
#include <numeric>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<vector<int>> hoge;
int main(){
    int a[8] = {};
    int n;
    cin >> n;
    int cnt = 0;
    int ans = 0;
    rep(i,n){
        int x;
        cin >> x;
        if(x<3200)a[x/400]++;
        else cnt++;
    }
    rep(i,8)if(a[i])ans++;
    cout << max(ans,1) << " " << ans+cnt << endl;
}


Measured memory_bytes: 256
int main(){
	long n,y,x,z;
	int i,j,k=0;

	scanf("%ld %ld", &n, &y);

	for(i=0; i<=n && k == 0; i++){
		for(j=0; j<=n && k == 0; j++){
			z = n - i - j;
			if(z>=0){
				x = 10000*i + 5000*j + 1000*z;
				if(y == x){
					printf("%d %d %ld\n", i, j, z);
					k=1;
					break;
				}
			}
			 
		}
	}

	if(k == 0) printf("-1 -1 -1\n");



  return 0;


}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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 namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;
const double PI = acos(-1.0);


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * b / g;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}



const int MAX_N = 100010;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k; cin >> n >> k;
	VE v(n); rep(i, n)cin >> v[i];
	int ans = 0;
	rep(i, n + 1) {
		rep(j, n + 1) {
			if (i + j > n || i + j > k)continue;
			VE tmp;
			rep(l, i) {
				tmp.push_back(v[l]);
			}
			rep(l, j) {
				tmp.push_back(v[n - l - 1]);
			}
			sort(ALL(tmp));
			int now = 0;
			rep(l, tmp.size()) {
				now += tmp[l];
			}
			int cnt = min((int)tmp.size(), k - (i + j));
			rep(l, cnt) {
				if (tmp[l] < 0)now -= tmp[l];
			}
			chmax(ans, now);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
H, W, K = map(int, input().split(' '))
C = []*H
ans=0
C = [list(input()) for _ in range(H)]
for paint_h in range(2**H):
    for paint_w in range(2**W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (paint_h>>i)&1==0 and (paint_w>>j)&1==0:
                    if C[i][j] == '#':
                        cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Measured memory_bytes: 9164
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
#define SortAsc(c) std::sort(c.begin(), c.end())
#define SortDesc(c) std::sort(c.rbegin(), c.rend())
int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};

bool isAllEven(vector<ll> &x)
{
    for (int i = 0; i < x.size(); i++)
    {
        if (x[i] % 2 == 1)
        {
            return false;
        }
    }

    return true;
}

string makeHash(vector<ll> &x)
{
    SortAsc(x);
    string h;
    h += to_string(x[0]) + "," + to_string(x[1]) + "," + to_string(x[2]);
    return h;
}

vector<ll> exchange(vector<ll> &x)
{
    vector<ll> n(3);

    n[0] = x[1] / 2 + x[2] / 2;
    n[1] = x[0] / 2 + x[2] / 2;
    n[2] = x[0] / 2 + x[1] / 2;

    return n;
}

int main()
{
    set<string> s;
    vector<ll> x(3);
    for (int i = 0; i < 3; i++)
    {
        cin >> x[i];
    }

    int count = 0;

    while (isAllEven(x))
    {
        string h = makeHash(x);
        if (s.count(h))
        {
            cout << -1 << endl;
            return 0;
        }

        s.insert(h);

        x = exchange(x);
        count++;
    }

    cout << count << endl;
}

Measured memory_bytes: 3708
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<complex>
#define lol(i,n) for(int i=0;i<n;i++)
#define out(x) cout<<(x?"Yes":"No")<<endl;
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    ll n,g;cin>>n>>g;
    ll a[20],b[20];lol(i,n)cin>>a[i]>>b[i];
    ll ans=mod;
    lol(i,(1<<n)){
	vector<int> v;v.clear();
	ll sum=0,cnt=0;
	lol(j,n){
	    if(i&(1<<j))sum+=(j+1)*100*a[j]+b[j],cnt+=a[j];
	    else lol(k,a[j])v.push_back((j+1)*100);
	}
	sort(v.begin(),v.end(),greater<int>());
	lol(j,v.size()){
	    if(sum>=g)break;
	    sum+=v[j],cnt++;
	}
	if(sum>=g)ans=min(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi atan(1.0)*4
#define pb(x) push_back(x)
#define in(x) insert(x)
#define fl(x,y) for(ll i=x;i<y;i++)
#define vi vector<long long>
#define vs  vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define fi first
#define se second
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
/*bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
LL bpow(LL a,LL b){if(b==0)return 1;LL r=bpow(a,b/2);if(b%2)return r*r*a;else return r*r;}
LL binpow(LL a,LL b){LL r=1;while(b>0){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
LL binpow(LL a,LL b,LL m){a%=m;LL r=1;while(b>0){if(b&1) r=r*a%m;a=a*a%m; b>>=1;}return r;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
*/
int main()
{
    ll X,R,m,a,b,c,d,x,y,z,w,t,n,k,p,q,r,sum,ct=0,flag=0;
    string s,s1,s2,s3,s4,s6="yellow",s5="red",s7;
    set<ll>st;
    cin>>t; ll mx=0;
    if(t%1000==0) {cout<<0<<endl; return 0;}
    p=t/1000;
    p+=1;
    p=p*1000;
    cout<<p-t<<endl;
}





Measured memory_bytes: 3620
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int n, i;
  int ai;
  int four = 0;
  int even = 0;
  int odd = 0;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%d", &ai);
    if(ai%4 == 0){
      four++;
    }else if(ai % 4 == 2){
      even++;
    }else{
      odd++;
    }
  }
  
  if((four + 1 >= odd && even == 0) || (four >= odd && even != 0)){
    printf("Yes");
  }else{
    printf("No");
  }

  return 0;
}


Measured memory_bytes: 128
n = int(input())
l = [int(x) for x in input().split()]
counter_1 = 0
counter_2 = 0
a = 1
for i in range(n):
  if l[i] == 0:
    counter_1 += 1
    print(0)
    break
if counter_1 == 0:
  for i in range(n):
    if counter_2 == 1:
      break
    else:
      a = a * l[i]
      if a > 10 ** 18:
        counter_2 +=1
        print(-1)
  if counter_2 == 0:
    print(a)


Measured memory_bytes: 21636
s = input()
K = int(input())
letters = []
for i in range(len(s)):
    for j in range(6):
        if(i + j > len(s)): break
        if(s[i:i + j] != ''): letters.append(s[i:i + j])
l = list(dict.fromkeys(letters))
l.sort()
print(l[K - 1])


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

using namespace std;

main(){
	int a,b,c,d,e;
	int k=0;
	int l=0;
	cin >>a >>b >>c >>d >>e;
	if (a < b && a < c){
		k=k+a;
	}
	else if (b < a && b < c){
		k=k+b;
	}
	else{
		k=k+c;
	}
	if (e > d){
		l=l+d;
	}
	else {
		l=l+e;
	}
	int g=k+l-50;
	printf("%d\n",g);
	}



Measured memory_bytes: 3200
#include <iostream>
#include <thread>
#include <chrono>
#include <random>
#include <fstream>
#include <time.h>

#define ll long long int
#define pr(x) (std::cout << x << std::endl)



int main()
{
    ll n;
    std::cin >> n;


    std::vector<int> v(200, 0);
    for(int i=0; i<200; i++){
        ll tmp = i+1, c = 1;
        while(tmp*c <= 200){
            v[tmp*c-1]++;
            c++;
        }
    }

    ll ans = 0;
    for(int i=0; i<n; i=i+2){
        if(v[i]==8) ans++;
    }
    pr(ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int beg[maxn],tto[maxn<<1],nex[maxn<<1],e;
void putin(int s,int t){
	tto[++e]=t;
	nex[e]=beg[s];
	beg[s]=e;
}
int d[maxn];
int dfs(int u,int fa){
	int sum=0,cnt=0,val;
	for(int i=beg[u];i;i=nex[i]){
		if(tto[i]==fa) continue;
		val=dfs(tto[i],u);
		sum+=val;
		if(val==0) cnt++;
	}
	if(cnt>1) sum+=cnt-1;
	return sum;
}
int main(){
//	freopen("E.in","r",stdin);
	int n;
	int s,t;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&s,&t);
		s++,t++;
		putin(s,t);
		putin(t,s);
		d[s]++,d[t]++;
	}
	int rt=0;
	for(int i=1;i<=n;i++){
		if(d[i]>=3){
			rt=i;
			break;
		}
	}
	if(!rt){
		printf("1\n");
		return 0;
	}
	int ans=dfs(rt,-1);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

void SayNo() {
    cout << "No" << endl;
}

int main() {

    string s;
    cin >> s;

    int n = s.length();
    // 回文である
    for (int i = 0; i < n; i++) {
        if (s[i] != s[n - 1 - i]) {
            SayNo();
            return 0;
        }
    }
    // 半分までが、回文である。
    int half = (n - 1) / 2;
    for (int i = 0; i < half - 1; i++) {
        if (s[i] != s[half - 1 - i]) {
            SayNo();
            return 0;
        }
    }
    // 半分以降が、回文である。
    int half2 = (n + 3) / 2;
    for (int i = half2 - 1; i < n; i++) {
        if (s[i] != s[n - 1 - (i - half2 + 1)]) {
            SayNo();
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;

}


Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
  n,m=parseMap(split(readline()))
  l=[parseMap(split(readline())) for i=1:n]
  sort!(l,by=x->x[1])
  have=0
  money=0
  for i in l
    if have+i[2]<m
      have+=i[2]
      money+=i[2]*i[1]
    else
      money+=(m-have)*i[1]
      break
    end
  end
  print(money)
end
main()

Measured memory_bytes: 155852