akhauriyash/Code-Regression huggingface dataset:
a = [list(map(int, input().split(' '))) for _ in range(3)]
n = int(input())
for _ in range(n):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if a[i][j] == b:
                a[i][j] = 0

for i in range(3):
    for j in a[i]:
        if j != 0:
            break
    else:
        print('Yes')
        break
    if a[0][i] == 0 and a[1][i] == 0 and a[2][i] == 0:
        print('Yes')
        break
    if a[0][0] == 0 and a[1][1] == 0 and a[2][2] == 0:
        print('Yes')
        break
    if a[0][2] == 0 and a[1][1] == 0 and a[2][0] == 0:
        print('Yes')
        break
else:
    print('No')

Measured memory_bytes: 3188
#include<bits/stdc++.h>
char s[200000];
int get[128];
int main()
{
    get['b'] = 0;
	get['p'] = 1;
	get['d'] = 2;
	get['q'] = 3;
    scanf("%s",s+1);
    for(int l=strlen(s+1),i=1;i<=(l>>1)+1;++i)
    {
        if(get[s[i]]^((get[s[l-i+1]]+2)%4))
		{
		return printf("No\n"),0;	
		 } 
    } 
    return printf("Yes\n"),0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder {
    class MainClass {
        public static void Main(string[] args) {

            var n = int.Parse(Console.ReadLine());

            var sArray = Console.ReadLine().Split(' ');
            var iArray = sArray.Select(int.Parse).ToArray();

            var count = bubbleSort(iArray, n);

            for(int i = 0; i < iArray.Length; i++) {

                if(i > 0) {

                    Console.Write(" ");

                }

                Console.Write(iArray[i]);

                if(i == iArray.Length - 1) {

                    Console.WriteLine("");

                }

            }

            Console.WriteLine(count);

        }

        static int bubbleSort(int[] a, int n) {

            var sw = 0;

            for(var i = 0; i < n; i++) {

                for(var j = n - 1; j >= i + 1; j--) {

                    if(a[j] < a[j-1]) {

                        var v = a[j - 1];
                        a[j - 1] = a[j];
                        a[j] = v;

                        sw++;
                    }

                }

            }

            return sw;

        }

        
    }
}



Measured memory_bytes: 18308
n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n - 1)]

adj = [[] for _ in range(n)]
for u, v, w in uvw:
    u -= 1
    v -= 1
    adj[u].append([v, w])
    adj[v].append([u, w])

stack = [0]
d = [-1] * n
d[0] = 0

while stack:
    u = stack.pop()
    for v, w in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + w
            d[v] %= 2
            stack.append(v)

print(*d, sep="\n")


Measured memory_bytes: 67244
x, y = gets.split.map(&:to_i)

ans = 0
if x < y
    if x >= 0 || y <= 0
        ans = y - x
    else
        if x.abs > y.abs
            ans = - y - x + 1
        else
            ans = y + x + 1
        end
    end
else
    if x < 0 || y > 0
        ans = x - y + 2
    else
        if x.abs > y.abs
            ans = y + x + 1
        else
            ans = - x - y + 1
        end
    end
end
puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

long long gcd(long long a, long long b){ // Ååöñ
    if(a == 0 || b == 0)
        return 0;
    if(b > a)
        swap(a, b);
    long long tmp;
    while((tmp = a % b) != 0){
        a = b;
        b = tmp;
    }
    return b;
}

long long lcm(long long a, long long b){ // Å¬ö{
    return a / gcd(a, b) * b;
}

long long solve(vector<vector<int> >& stick, int i)
{
    if(i == 0)
        return 1;

    long long p = stick[i][0];
    long long q = stick[i][1];

    long long a = solve(stick, stick[i][2]);
    long long b = solve(stick, stick[i][3]);
    long long tmp = lcm(p*a, q*b);
    a = tmp / p;
    b = tmp / q;

    return a + b;
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<vector<int> > stick(n+1, vector<int>(4));
        vector<bool> check(n+1, false);
        for(int i=1; i<=n; ++i){
            for(int j=0; j<4; ++j){
                cin >> stick[i][j];
            }
            check[stick[i][2]] = check[stick[i][3]] = true;
        }

        long long ret = 0;
        for(int i=1; i<=n; ++i){
            if(!check[i])
                ret += solve(stick, i);
        }
        cout << ret << endl;
    }
}

Measured memory_bytes: 0
package main

import "fmt"

func main() {
	var n, k, q, a int
	fmt.Scanln(&n, &k, &q)
	scores := make([]int, n)
	for i := 0; i < q; i++ {
		fmt.Scanln(&a)
		scores[a-1]++
	}
	for _, v := range scores {
		score := v - q + k
		if score > 0 {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}
}


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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define DBG(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define DBG(...)
#endif

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, n) for (auto i : (n))
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int main() {
  int N;
  cin >> N;
  cout << (N + 1) / 2 << endl;
}


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

const double PI = acos(-1);
const double EPS = 1e-15;
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
const ll MOD1 = 998244353;
//typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int n;
int a[200010];
ll sum[200010];
ll dp[200010];

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

  cin >> n;
  dp[0] = 1;
  REP(i,n) cin >> a[i+1];
  REP(i,n) {
    if (a[i+1] == a[i]) {
      dp[i+1] = dp[i];
      continue;
    }
    dp[i+1] = (dp[i] + sum[a[i+1]]) % MOD;
    sum[a[i+1]] += dp[i];
    sum[a[i+1]] %= MOD;
  }
  cout << dp[n] << endl;
  return 0;
}


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

int n, K, q, a[2010];

int main() {
    scanf("%d %d %d", &n, &K, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        auto chk = [&](int x) {
            vector<int> V;
            for (int l = 1, r = 1; l <= n; l = r) {
                vector<int> num;
                while (l <= n && a[l] < x) l++;
                r = l;
                while (r <= n && a[r] >= x) r++;
                for (int i = l; i <= min(r - 1, n); i++) num.push_back(a[i]);
                if (num.size() >= K) {
                    sort(num.begin(), num.end());
                    for (int i = 0; i <= num.size() - K; i++) V.push_back(num[i]);
                }
            }
            sort(V.begin(), V.end());
            if (V.size() >= q) ans = min(ans, V[q - 1] - V[0]);
        };
        chk(a[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
/*******************************************************************
 * 		Author : yash1402_										   *
 ******************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

#define MOD 1000000007

void solve() {
	ll n;
	cin >> n;
	vll v(n);
	
	for(auto &i:v) cin >> i;
	
	ll s=0,ans = 0;
	
	for(ll i=0;i<n;i++) {
		s = s+v[i];
	}
	
	for(ll i=0;i<n-1;i++) {
		s -= v[i];
		ans = (ans + (( (v[i]%MOD)*(s%MOD) )%MOD))%MOD;
	}
	
	cout << ans << "\n";
}

int main() {
	ll T=1;
	//cin >> T;
	while(T--) {
		solve();
	}
}



Measured memory_bytes: 4836
s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()

status = {s:a, t:b}

for k, v in status.items():
    if u == k:
        status[k] = status[k] - 1

print(str(status[s]) + ' ' + str(status[t]))

Measured memory_bytes: 3060
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 0; t < T; ++t) {
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int n = 0; n < N; ++n) {
            cin >> A[n];
        }
        string S;
        cin >> S;
        set<ll, greater<ll>> Set;
        for (int n = N-1; n >= 0; --n) {
            if (S[n] == '0') {
                ll Tmp = A[n];
                for (auto s : Set) {
                    Tmp = min(Tmp, Tmp^s);
                }
                if (Tmp) {
                    Set.insert(Tmp);
                }
            } else {
                ll Tmp = A[n];
                for (auto s : Set) {
                    Tmp = min(Tmp, Tmp^s);
                }
                if (Tmp) {
                    Set.clear();
                    break;
                }
            }
        }
        if (Set.empty()) {
            cout << '1' << endl;
        } else {
            cout << '0' << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
int isprime(int x);
int main(void){
	int n;
	int cnt;
	int i,j;
	int x;
	cin>>n;
	cnt=0;
	for(i=0;i<n;i++){
		cin>>x;
		if(isprime(x))	cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}
int isprime(int x){
	int i;
	if(x==2)	return 1;
	if(x<2)	return 0;
	if(x%2==0)	return 0;
	for(i=3;i*i<=x;i+=2){
		if(x%i==0)	return 0;
	}
	return 1;
}
	


Measured memory_bytes: 3084
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#include<set>
#include<limits.h>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<functional>
#include<stack>
#include<deque>
#include<queue>
#define int long long
#define P pair<int,int>
using namespace std;

int BIT[100002];
void add(int a) {
	while (a <= 100000) {
		BIT[a]++;
		a += a&-a;
	}
}
int Sum(int a) {
	int b = 0;
	while (a > 0) {
		b += BIT[a];
		a -= a&-a;
	}
	return b;
}
int b[26];
int d[26];
vector<int>p[26], q[26];
vector<P>V;
signed main() {
	string a; cin >> a;
	for (char c : a) {
		b[c - 'a']++;
	}
	int sum = 0;
	for (int i = 0; i < 26; i++) {
		if (b[i] & 1)sum++;
	}
	if (a.length() & 1) {
		if (sum != 1) {
			puts("-1");
			return 0;
		}
		string l, r;
		int ans = 0;
		for (int i = 0; i < a.length(); i++) {
			d[a[i] - 'a']++;
			if (d[a[i] - 'a'] * 2 - 1 == b[a[i] - 'a']) {
				for (int j = 0; j < 26; j++) {
					if(a[i] - 'a'!=j)
					ans += abs(b[j] / 2 - d[j]);
				}
			}
			else if (d[a[i] - 'a'] * 2 <= b[a[i] - 'a']) {
				l += a[i];
			}
			else {
				r += a[i];
				for (int j = 0; j < 26; j++) {
					ans += max(0ll, b[j] / 2 - d[j]);
				}
			}
		}
		reverse(r.begin(), r.end());
		for (int i = 0; i < l.length(); i++) {
			p[l[i] - 'a'].push_back(i);
			q[r[i] - 'a'].push_back(i);
		}
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < p[i].size(); j++) {
				V.push_back({ p[i][j],q[i][j] });
			}
		}
		sort(V.begin(), V.end(), greater<P>());
		for (int i = 0; i < V.size(); i++) {
			ans += Sum(V[i].second + 1);
			add(V[i].second + 2);
		}
		cout << ans << endl;
	}
	else {
		if (sum != 0) {
			puts("-1");
			return 0;
		}
		string l, r;
		int ans = 0;
		for (int i = 0; i < a.length(); i++) {
			d[a[i] - 'a']++;
			if (d[a[i] - 'a'] * 2 <= b[a[i] - 'a']) {
				l += a[i];
			}
			else {
				r += a[i];
				for (int j = 0; j < 26; j++) {
					ans += max(0ll, b[j] / 2 - d[j]);
				}
			}
		}
		reverse(r.begin(), r.end());
		for (int i = 0; i < l.length(); i++) {
			p[l[i] - 'a'].push_back(i);
			q[r[i] - 'a'].push_back(i);
		}
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < p[i].size(); j++) {
				V.push_back({ p[i][j],q[i][j] });
			}
		}
		sort(V.begin(), V.end(), greater<P>());
		for (int i = 0; i < V.size(); i++) {
			ans += Sum(V[i].second + 1);
			add(V[i].second + 2);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 5872
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		String a = scan.next();
		String b = scan.next();
		if(a.equals("H")){
			if(b.equals("H")){
				System.out.println("H");
			}
			else{System.out.println("D");}
		}
		if(a.equals("D")){
			if(b.equals("D")){
				System.out.println("H");
			}
			else{System.out.println("D");}
		}



	}
}

Measured memory_bytes: 22100
#!/usr/bin/env python3
s = input()
if s[0] == s[1] == s[2] == s[3]:
    print('No')
elif (s[0] == s[1] and s[2] == s[3]) or (s[0] == s[2] and s[1] == s[3]) or (s[0] == s[3] and s[1] == s[2]):
    print("Yes")
else:
    print('No')


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

const int INF = 1001001001;

int a[12][12];

int main() {
 string S;
 cin>>S;
 for(int i=0;i<S.size()-1;i++){
   if(S.substr(i,2)=="AC"){cout<<"Yes"<<endl;return 0;}
 }
   cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.PriorityQueue
import kotlin.comparisons.compareByDescending
fun main(args: Array<String>) {
    val N = nextInt()
    val A = listOfLong()
    //前半
    val first = fun(): LongArray {
    	val array = LongArray(N + 1)
    	val Q = PriorityQueue<Long>(N)
    	Q.addAll(A.subList(0, N))
    	var S = Q.toList().sum()
    	for (n in 0 .. N) {
        	array[n] = S
        	S += A[N + n]
        	Q.add(A[N + n])
        	S -= Q.poll()!! //一番小さい引く
    	}
    	return array
	}()
    //後半
    val latter = fun(): LongArray {
	    val array = LongArray(N + 1)
    	val Q = PriorityQueue<Long>(N, compareByDescending { it })
    	Q.addAll(A.subList(2 * N, 3 * N))
    	var S = Q.toList().sum()
    	for (n in 0 .. N) {
        	array[N - n] = S
        	S += A[2 * N - n - 1]
        	Q.add(A[2 * N - n - 1])
        	S -= Q.poll()!! // 一番大きい引く
    	}
    	return array
    }()
    var ans = (0 .. N).map { first[it] - latter[it] }.max()!!
    println(ans)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfInt(vararg deltas: Int) = listOfString().map { Integer.parseInt(it) }.mapIndexed { index, int -> int + deltas[index % deltas.size] }
fun listOfLong(offset: Long = 0L) = listOfString().map { it.toLong() + offset}


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

#define ll long long int
 
int main() {
    ll n, k, MOD = 1e9 + 7;
    cin >> n >> k;
    vector<ll> sum(200002, 0);
    for(ll i = 1; i <= 200002; i++) {
        sum[i] = sum[i - 1] + i;
    }
    ll ans = 0;
    for(ll i = k; i <= n + 1; i++) {
        ll mn = sum[i], mx = sum[n + 1] - sum[n + 1 - i];
        // cout << mx << " " << mn << endl;
        ans = (ans + (mx - mn + 1) % MOD) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4848
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    ans += n/25;
    n %= 25;
    ans += n/10;
    n %= 10;
    ans += n/5;
    n %= 5;
    ans += n;
    cout << ans << endl;
}


Measured memory_bytes: 3232
using System;

class MyClass
{
    static int IsPrime(int a)
    {
        for (int i = 2; i <= Math.Sqrt(a); i++)
        {
            if (a % i == 0)
            {
                return 0;
            }
        }
        return 1;
    }

    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int num = 0;
        for (int i = 0; i < N; i++)
        {
            num += IsPrime(int.Parse(Console.ReadLine()));
        }
        Console.WriteLine(num);
    }
}


Measured memory_bytes: 5660
#include<stdio.h>
 
#define BLACK -1
#define GRAY  -2
#define WHITE -3
 
void DFSvisit(int);
 
int G[100][100],d[100],f[100],color[100];
int n,time;
 
void DFS(int n){
  int i;
 
  for(i=0;i<n;i++){
    if(color[i]==WHITE){
      DFSvisit(i);
    }
  }
}
 
void DFSvisit(int u){
  int i;
 
  color[u]=GRAY;
  time++;
  d[u]=time;
 
  for(i=0;i<=n;i++){
    if(G[u][i] && color[i]==WHITE){
      DFSvisit(i);
    }
  }
  color[u]=BLACK;
  f[u]=++time;
}
 
main(){
  int  i,j,k,m;
 
  scanf("%d",&n);
 
  for(i=0;i<100;i++){
    for(j=0;j<100;j++){
      G[i][j]=0;
    }
    color[i] = WHITE;
  }
 
  for(i=0;i<n;i++){
    scanf("%d%d",&j,&k);
    for(j=0;j<k;j++){
      scanf("%d",&m);
      G[i][m-1]=1;
    }
  }
  
  DFS(n);
 
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(3));
  vector<vector<int>> dp(n + 1, vector<int>(3, 0));

  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
  }
  dp[0][0] = a[0][0];
  dp[0][1] = a[0][1];
  dp[0][2] = a[0][2];
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if (j == k) {
          continue;
        }
        if (dp[i][j] + a[i + 1][k] > dp[i + 1][k]) {
          dp[i + 1][k] = dp[i][j] + a[i + 1][k];
        }
      }
    }
  }
  int x, y, z;
  x = dp[n - 1][0];
  y = dp[n - 1][1];
  z = dp[n - 1][2];
  cout << max({x, y, z}) << endl;
  /*for (int i = 0; i < n;i++){
    cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
  }*/
  return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = y.pow(y, n);
  Mint pow(Mint a, long long n) const {
    Mint y(1);
    Mint b(a);
    while (n > 0) {
      if (n & 1) y *= b;
      b *= b;
      n >>= 1;
    }
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return pow(a, mod-2);
  }

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

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= i;
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<long long > A(N);
  long long sum = 0;
  for (int i=0; i<N; i++) {
    std::cin >> A[i];
    sum += A[i];
  }
  std::vector<long long > yakusuu;
  for (long long i=1; i*i<=sum; i++) {
    if (sum%i==0) {
      yakusuu.push_back(i);
      if (i*i!=sum) {
        yakusuu.push_back(sum/i);
      }
    }
  }
  std::sort(yakusuu.rbegin(), yakusuu.rend());
  for (long long y : yakusuu) {
    //printf("y=%lld\n", y);
    std::vector<long long > AA(N);
    for (int i=0; i<N; i++) {
      AA[i] = A[i]%y;
    }
    std::sort(AA.begin(), AA.end());
    int left = 0;
    int right = N-1;
    long long negative_sum = 0;
    long long positive_sum = 0;
    while(right>left) {
      while(negative_sum <= positive_sum) {
        negative_sum += AA[left];
        //printf("nega=%lld\n", negative_sum);
        left++;
        if (right<left) break;
      }
      while(positive_sum < negative_sum) {
        positive_sum += y - AA[right];
        right--;
        if (right<left) break;
      }
    }
    //printf("negative=%lld, positive_sum=%lld\n", negative_sum, positive_sum);
    if (positive_sum<=K) {
      printf("%lld\n", y);
      return 0;
    }
  }
  return 0;
}

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

int main() {
    string s;
    cin>>s;
    
    if(s=="Sunny") cout<<"Cloudy"<<endl;
    else if(s=="Cloudy") cout<<"Rainy"<<endl;
    else cout<<"Sunny"<<endl;
    
    return 0;
} 

Measured memory_bytes: 256
import sys

n = int(input())

for i in range(1, 3500):
    for j in range(1, 3500):
        rest = 4 * i * j - (i + j) * n
        if rest > 0:
            ans = n * i * j / rest
            if ans.is_integer():
                print(i, j, int(ans))
                sys.exit()

Measured memory_bytes: 9088
//code by lynmisakura.wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
char maze[20][20];
vector<int> g[400];
int h,w;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

int gr[400][400];

int main(int argc, char const *argv[])
{
    scanf("%d %d",&h,&w);
    for (int i = 0; i < 400; ++i)
    {
        for (int j = 0; j < 400; ++j)
        {
            gr[i][j] = 2000;
        }
    }

    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            cin >> maze[i][j];
        }
    }
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if(maze[i][j] == '#')continue;
            int num = i*w + j;
            for (int k = 0; k < 4; ++k)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(nx >= 0 and nx < h and ny >= 0 and ny < w){
                    if(maze[nx][ny] == '.'){
                        gr[num][nx*w+ny] = 1;
                    }
                }
            }
        }
    }
    for(int k = 0;k < h*w;k++){
        for(int i = 0;i < h*w;i++){
            for(int j = 0;j < h*w;j++) gr[i][j] = min(gr[i][j],gr[i][k] + gr[k][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < h*w; ++i)
    {
        for (int j = 0; j < h*w; ++j)
        {

//            cout << gr[i][j] << " ";
            if(i == j or gr[i][j] >= 1000)continue;
            else ans = max(ans,gr[i][j]);

//            if(ans == 2)cout << i << " " << j << endl;
        }
//        cout << endl;
    }
//    cout << gr[5][7] << endl;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define pb push_back
#define fi first
#define se second

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

const int mod = 998244353;
int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int MAXN = 2e5 + 5;

int a[MAXN], f[MAXN];

int n;
int M(int i) {
  return (i + n) % n;
}

bool check(int i) {
  return a[i] > a[M(i + 1)] && a[i] > a[M(i - 1)];
}

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

  cin >> n;
  REP(i, n) cin >> f[i];
  REP(i, n) cin >> a[i];

  vector<int> good;
  REP(i, n) {
    if(check(i)) {
      good.pb(i);
    }
  }

  ll sol = 0;

  while(good.size()) {
    int i = good.back();
    good.pop_back();

    int sums = a[M(i + 1)] + a[M(i - 1)];
    int times = max(0, (a[i] - max(f[i], max(a[M(i + 1)], a[M(i - 1)])) - 1)) / sums;

    if(a[i] == f[i]) times --;

    times ++;
    sol += times;

    a[i] -= times * sums;
    if(check(M(i + 1))) good.pb(M(i + 1));
    if(check(M(i - 1))) good.pb(M(i - 1));
  }

  REP(i, n) if(a[i] != f[i]) {
    cout << -1 << endl;
    return 0;
  }

  cout << sol << endl;
}


Measured memory_bytes: 2428
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=305;
char ss[N][N];
int n,m;
int f[N][N][1205];
int g[N][N][1205];
int calc (int x1,int y1,int x2,int y2,int d)//这个矩形里面的答案 
{
	if (x1>x2) return 0;
	if (y1>y2) return 0;
	return f[x2][y2][d+600]-f[x2][y1-1][d+600]-f[x1-1][y2][d+600]+f[x1-1][y1-1][d+600];
}
int calc1 (int x1,int y1,int x2,int y2,int d)
{
	if (x1>x2) return 0;
	if (y1>y2) return 0;
//	printf("YES\n");
	return g[x2][y2][d+600]-g[x2][y1-1][d+600]-g[x1-1][y2][d+600]+g[x1-1][y1-1][d+600];
}
bool check (int x,int y)	{return x<=n&&y<=m&&x>=1&&y>=1&&ss[x][y]=='#';}
int main()
{
	scanf("%d%d",&n,&m);
	for (int u=1;u<=n;u++)	scanf("%s",ss[u]+1);
	for (int u=1;u<=n;u++)
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=1200;j++)
			{
				f[u][i][j]=f[u][i][j]+f[u][i-1][j]+f[u-1][i][j]-f[u-1][i-1][j];
				g[u][i][j]=g[u][i][j]+g[u][i-1][j]+g[u-1][i][j]-g[u-1][i-1][j];
			}
			if (ss[u][i]=='#')	
			{
				f[u][i][u+i+600]++;
				g[u][i][u-i+600]++;
			}
		}
	//	printf("%lld\n",calc1(4,3,4,1,2));
	LL ans=0;
	for (int u=1;u<=n;u++)
		for (int i=1;i<=m;i++)
			{
				for (int d=1;d<=min(n,m);d++)
				{
					if (check(u,i+d)&&check(u+d,i))	ans=ans+calc(1,1,u,i,u+i-d);
				//	if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					if (check(u,i-d)&&check(u+d,i))	
					{
						//if (u==2&&i==3&&d==1) printf("%lld %lld %lld %lld %lld\n",1,i,u,m,calc1(1,i,u,m,u-i-d));
						ans=ans+calc1(1,i,u,m,u-i-d);
						//if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					}
					if (check(u,i+d)&&check(u-d,i)) 
					{
					//	if (u==4&&i==3&&d==1) printf("%lld %lld %lld %lld %lld %lld\n",n,i,u,1,d+u-i,calc1(n,i,u,1,d+u-i));
						ans=ans+calc1(u,1,n,i,d+u-i);
						//if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					}
					if (check(u,i-d)&&check(u-d,i)) ans=ans+calc(u,i,n,m,d+u+i);
				//	if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					int cnt=0;
					cnt=cnt+check(u,i+d)+check(u+d,i)+check(u-d,i)+check(u,i-d);
					if (cnt==4) ans=ans-4;
					if (cnt==3) ans--;
				}
				//printf("%lld %lld %lld\n",u,i,ans);
			}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 863232
# ARC080C - 4-adjacent (ABC069C)
def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    f, t, m = 0, 0, 0  # two, four, misc
    for i in A:
        if i % 4 == 0:
            f += 1
        elif i % 2 == 0:
            t += 1
        else:
            m += 1
    m += t % 2
    print("Yes" if m - f <= 1 else "No")


if __name__ == "__main__":
    main()

Measured memory_bytes: 14352
n = int(input())
x = list(int(i) for i in input().split())
N = 0
ans=0
for i in range(n):
	N+=x[i]

for i in range(n):
	ans+=(x[i]-N//n)**2

if N%n ==0:
	print(ans)
else:
	print(min(ans,ans+n-2*N+2*(N//n)*n))


Measured memory_bytes: 3060
using System;

class Program
{
    static void Main(string[] args) {
        int N = int.Parse(Console.ReadLine());
        string[] a = Console.ReadLine().Split(' ');

        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = int.Parse(a[i]);
        }

        for (int i = 1; i < N; i++) {
            int v = A[i];
            int j = i - 1;

            DisplayArray(A);

            while (j >= 0 && A[j] > v) {
                A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = v;
        }

        DisplayArray(A);
    }

    static void DisplayArray(int[] A) {
        for (int i = 0; i < A.Length; i++) {
            if (i > 0) { Console.Write(" "); }
            Console.Write(A[i]);
        }
        Console.WriteLine("");
    }
}



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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

// 最大公約数 : 3,4 ->  1
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 最小公倍数 : 3,4 -> 12
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

// a 以上 b 以下の数のうち c で割り切れるものの個数
ll ranged_div_num(ll a, ll b, ll c)
{
	return (b / c - (a-1) / c);
}


void solve()
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll ans = b - a + 1;
	cout << ans - ( ranged_div_num(a, b, c) + ranged_div_num(a, b, d) - ranged_div_num( a, b, lcm(c, d) ) );
}

int main()
{
	fastio;
	solve();

	return 0;
}

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

int H, W;
char A[10][10];
bool visited[10][10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool dfs(int x, int y) {
    visited[x][y] = true;
    if (x == H-1 && y == W-1) {
        return true;
    }
    else {
        for (int i = 0; i < 4; i++) {
            if (0 <= x+dx[i] && x+dx[i] < H &&
                0 <= y+dy[i] && y+dy[i] < W) {
                if (A[x+dx[i]][y+dy[i]] == '#') {
                    if (!visited[x+dx[i]][y+dy[i]] && i < 2) {
                        return dfs(x+dx[i], y+dy[i]);
                    }
                } 
            }
        }
    }
    return false;
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> A[i][j];
        }
    }
    memset(visited, false, sizeof(visited));

    bool c = dfs(0, 0);
    bool d = true;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (A[i][j] == '#' && !visited[i][j]) {
                d = false;
            }
        }
        if (!d) break;
    }

    cout << (c && d ? "Possible" : "Impossible") << endl;
  
    return 0;
}


Measured memory_bytes: 256
// AOJ 3041: Round And Round
// 2019.2.22 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n)
{
	int i;
	char ob[20];

	if (!n) pc('0');
	else {
		i = 0; while (n) ob[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(ob[i]);
	}
	pc('\n');
}

int main()
{
	int a, N, Q, q, k;

	N = in(), Q = in();
	a = 0;
	while (Q--) {
		q = gc(), gc();
		k = in();
		if (q & 1) {
			a += k;
			if (a >= N) a -= N;
		}
		else out(1 + (a + k - 1) % N);
	}
	return 0;
}


Measured memory_bytes: 2064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

int main()
{

  vector<int> t(4);
  cin >> t[0] >> t[1] >> t[2] >> t[3];

  int alice_time = t[1] - t[0];
  int bob_time = t[3] - t[2];
  int cross_time;

  sort(t.begin(), t.end());
  int max_time = t[3] - t[1];
  if( max_time >= (alice_time + bob_time) ){
    cross_time = 0;
  }
  else{ cross_time = t[2] - t[1]; }

  cout << cross_time << endl;

  return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
 
#define PI 3.1415926535897932384626433832795
#define M 0.01745329251994329576923690768489
 
#define EPS  1.0e-8
#define isZero(k) (fabs(k) <= EPS)
 
int main()
{
    double r, q, f;
    int d, a;
    double r2, q2, t;
 
    r = 0, q = 90*M, f = 0;
    while (1) {
        scanf("%d,%d", &d, &a);
        if (!d && !a) break;
        r2 = sqrt(r*r + d*d - 2*r*d*cos(PI - fabs(f)));
        if (isZero(r) || isZero(r2)) q2 = q - f, f = a*M;
        else {
            t = acos((r*r + r2*r2 - d*d) / (2 * r*r2));
            if (f >= 0) q2 = q - t, f += a*M - t;
            else        q2 = q + t, f += a*M + t;
        }
        r = r2, q = q2;
    }
    printf("%d\n%d\n", (int)(r * cos(q)), (int)(r * sin(q)));
    return 0;
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
     
#define ll long long
#define loop(i,a,n) for(ll i=a;i<n;++i)
#define revloop(i,a,b) for(ll i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 9999999999999999
#define MOD 1000000007

void func()
{
    ll n;
    cin>>n;
    ll a[n],sum=0;
    loop(i,0,n){
        cin>>a[i];
        sum+=a[i];
    }
    ll ans=0;
    loop(i,0,n){
        sum=sum-a[i];
        ans=(ans % MOD + (a[i]*(sum % MOD)) % MOD) % MOD;
    }
    cout<<ans<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
 
    ll t=1;
    //cin>>t;
    //solve();
    while(t--)
    {
        func();
    }

}


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

using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;

// Debug
#ifdef SANYAM1101
	struct debug_printer{
		template<typename T, typename = void>
		struct is_ostreamable : std::false_type {};

		template<typename T>
		struct is_ostreamable<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T>())>> : std::true_type {};

		template<typename T, std::enable_if_t<is_ostreamable<T>::value, int> = 0>
		debug_printer& operator << (const T& t) {
			std::cerr << std::fixed << std::setprecision(20) << std::boolalpha << t; return *this;
		}

		template<typename T, typename U>
		debug_printer& operator << (const std::pair<T,U>& p) {
			return *this << "(" << p.first << " => " << p.second << ")";
		}

		template<typename T, std::enable_if_t<not is_ostreamable<T>::value, int> = 0>
		debug_printer& operator << (const T& container) {
			*this << "[";
			for(const auto& i: container) *this << i << ", ";
			return *this << (container.begin() != container.end() ? "\b\b]" : "]");
		}
	};

	template<typename Head, typename... Tail>
	void debug_f(std::string str, Head H, Tail... T) {
		debug_printer() << "\t" << str.substr(0, str.find(", ")) << " <=> " << H << "\n";
		if constexpr(sizeof...(T)) debug_f(str.substr(str.find(", ") + 2), T...);
	}

	#define trace(args...) do{ debug_printer() << "Line #" << __LINE__ << "\n"; debug_f(#args, args); } while(0)
#else
	#define trace(args...)
#endif

int grid[3000][3000];
ll dp[3000][3000][4];

void solve(){
	int r, c, k;
	cin >> r >> c >> k;

	while(k--){
		int x, y, cost;
		cin >> x >> y >> cost;
		grid[x - 1][y - 1] = cost;
	}

	for(int i = r - 1; i >= 0; --i){
		for(int j = c - 1; j >= 0; --j){
			for(int taken = 0; taken < 4; ++taken){
				ll not_taking = 0;
				if(i + 1 < r) not_taking = max(not_taking, dp[i + 1][j][3]);
				if(j + 1 < c) not_taking = max(not_taking, dp[i][j + 1][taken]);
				dp[i][j][taken] = not_taking;

				if(taken == 0) continue;

				ll taking = 0;
				if(i + 1 < r) taking = max(taking, dp[i + 1][j][3]);
				if(j + 1 < c) taking = max(taking, dp[i][j + 1][taken - 1]);
				dp[i][j][taken] = max(dp[i][j][taken], grid[i][j] + taking);
			}
		}
	}

	cout << dp[0][0][3];
}

signed main (void){
	// Fast_IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// Set Fixed Notation (default sucks), High Precision for Floating-Point Output
	cout << fixed << setprecision(20);

	// Multiple TCs
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}


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

int main()
{
    multimap<ll, ll> pq;
    ll n, m;
    cin >> n >> m;

    for (ll i = 0; i < n; i++) {
        ll coin, num;
        scanf("%lld %lld", &coin, &num);

        pq.insert({coin, -num});
    }

    ll cnt = 0;
    ll koyta_nilam = 0;
    for (auto tmp : pq) {

        ll curcoin = tmp.first;
        ll curnum = -tmp.second;

        if (curnum + koyta_nilam > m) cnt += (m - koyta_nilam) * curcoin, koyta_nilam = m;
        else cnt += curnum * curcoin, koyta_nilam += curnum;

        if (koyta_nilam == m) break;
    }

    cout << cnt << endl;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
 
const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;
           
int kol = 1;

int a,b;

int ans;

int main()
{
	cin >> a >> b;
	while (kol < b)
	{
		ans++;
		kol--;
		kol += a;	
	}
	cout << ans;

}


Measured memory_bytes: 256
// 2020-08-30 17:28:30
// clang-format off
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

// clang-format on
void answer() {
  int h, w, d;
  cin >> h >> w >> d;
  vector<P> a(h * w + 10);
  rep(i, h) rep(j, w) {
    int x;
    cin >> x;
    a[x] = P(i, j);
  }
  vector<ll> dp(h * w + 10, 0);
  REPC(i, d + 1, h * w) {
    int j = i - d;
    dp[i] =
        dp[j] + abs(a[i].first - a[j].first) + abs(a[i].second - a[j].second);
  }
  int q;
  cin >> q;
  rep(qi, q) {
    int l, r;
    cin >> l >> r;
    cout << dp[r] - dp[l] << '\n';
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 4452
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl "\n"
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)

using namespace std;

typedef unsigned long long ull;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;

const int MAXN = 150;
const int MAXW = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

int add(int x, int y) { return ((x % MOD)  + (y % MOD)) % MOD;             }
int mul(int x, int y) { return ((x % MOD) * (long long)(y % MOD)) % MOD;   }
int sub(int x, int y) { return add(x, -y + MOD);                           }

ll n, W, w[MAXN], v[MAXN];

ll dp[MAXN][MAXW];

ll solve(ll x, ll curW) {
	if(curW < 0) return -INF;
	if(x == 0 || curW == 0) return 0;
	if(x >= 0 && curW >= 0 && dp[x][curW] != -1) return dp[x][curW];
	return dp[x][curW] = max(v[x] + solve(x - 1, curW - w[x]), solve(x - 1, curW));
}

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

	cin >> n >> W;

	memset(dp, -1, sizeof dp);

	for(int i = 1 ; i <= n ; ++i) {
		cin >> w[i] >> v[i];
	}

	cout << solve(n, W) << endl;



	return 0;
}




Measured memory_bytes: 117504
def B_Minesweeper(H, W, S):
    # 書き換え後のフィールド
    board = S.copy()
    # ある点の右、下、左、上、右下、左下、左上、右上
    dx = (1, 0, -1, 0, 1, -1, -1, 1)
    dy = (0, 1, 0, -1, 1, 1, -1, -1)

    for i in range(H):
        for j in range(W):
            if board[i][j] == '#':
                continue

            num = 0  # 周囲8マスの#の数
            for k in range(8):
                y = i + dy[k]
                x = j + dx[k]

                if x < 0 or W <= x:
                    continue
                if y < 0 or H <= y:
                    continue
                if board[y][x] == '#':
                    num += 1
            board[i] = board[i][:j] + chr(ord('0') + num) + board[i][j+1:]

    for s in board:
        print(''.join(s))
    return None
  
H,W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
B_Minesweeper(H, W, S)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
c=0
for _ in range(N):
    d=list(map(int,input().split()))
    if d[0]==d[1]:
        c+=1
    else:
        c=0
    if c==3:
        print('Yes')
        exit()
print('No')

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S; cin >> S;
    int ans = 0;
    stack<char> st;
    rep(i, S.length()){
        if(st.empty()) st.push(S[i]);
        else{
            if(st.top() != S[i]){
                st.pop();
                ans += 2;
            }
            else st.push(S[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#define ll long long
#define min(p,q)((p)<(q)?(p):(q))

ll ans=2e18;
ll f(ll a,ll s){
	if(a%2)return s;
	else return 0;
}

int main(){
	ll a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	ans=min(ans,f(a,b*c));
	ans=min(ans,f(b,a*c));
	ans=min(ans,f(c,b*a));
	printf("%lld",ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, m; cin >> n >> m;
    set<ll> from1, ton;
    rep(i, m) {
        ll a, b; cin >> a >> b;
        if (a == 1) from1.insert(b);
        if (b == n) ton.insert(a);
    }

    vector<ll> result(from1.size() + ton.size());
    auto it = set_intersection(from1.begin(), from1.end(), ton.begin(), ton.end(), result.begin());
    result.resize(it - result.begin());
    if (result.size() > 0) {
        cout << "POSSIBLE" << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

Measured memory_bytes: 11136
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;
using namespace std;

int main(){
    int N; cin >> N;
    cout << N * N * N<< endl;
    return 0;
}




Measured memory_bytes: 256
//全探索してしまえばいいという問題

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ll X;
  cin >> X;

  for (ll i = -1000; i <= 1000; i++) {
    for (ll j = -1000; j <= 1000; j++) {
      ll ans = i * i * i * i * i - j * j * j * j * j;
      if (ans == X) {
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3648
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

x = ir()
tmp = x
ans = 0
while tmp > 0:
    ans += 1
    tmp-=ans
print(ans)

Measured memory_bytes: 72720
N, K = map(int, input().split())
ans = []
rest = (N-1) * (N-2) / 2 - K
if rest < 0:
    print(-1)
else:
    ans.append([1, 2])
    tmp = 1
    for i in range(3, N+1):
        ans.append([1, i])

    i = 2
    while rest > 0:
        j = i + 1
        while True:
            ans.append([i, j])
            j += 1
            rest -= 1
            if rest == 0 or j > N:
                break
        i += 1

    print(len(ans))
    for i in range(len(ans)):
        print(ans[i][0], ans[i][1])


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

int main() {
  int n; cin >> n;
  vector<int> ans(26, 51);
  for (int i = 0; i < n; i++) {
    string s; cin >> s;
    vector<int> cnt(26, 0);
    for (int j = 0; j < s.size(); j++) cnt.at(s.at(j) - 'a')++;
    for (int j = 0; j < 26; j++) ans.at(j) = min(ans.at(j), cnt.at(j));
  }
  string alp = "abcdefghijklmnopqrstuvwxyz";
  for (int i = 0; i < 26; i++) {
    if (ans.at(i) == 0) continue;
    for (int j = 0; j < ans.at(i); j++) cout << alp.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100 + 5;
const int M = 1e5 + 5;
bool dp[M];
int n, k;
int arr[N];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i <= k; i++)
        for (int j = 0; j < n; j++)
            if (i - arr[j] >= 0 && !dp[i - arr[j]])
                dp[i] = true;
    puts(dp[k] ? "First" : "Second");
    return 0;
}


Measured memory_bytes: 384
import numpy as np
import math


A, B, H, M = map(int, input().split())

d = np.sqrt((B*math.cos(math.radians(6*M))-A*math.cos(math.radians(30*H+M/2)))**2+(B*math.sin(math.radians(6*M))-A*math.sin(math.radians(30*H+M/2)))**2)
print(d)

Measured memory_bytes: 27168