akhauriyash/Code-Regression huggingface dataset:
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n;
int arr[404];
int sum[404];
int cache[404][404];
int dp(int l,int r)
{
    if(r==l)
        return 0;
    int &ans=cache[l][r];
    if(ans!=-1)
        return ans;
    ans=1e18;
    for(int i=l;i<=r-1;i++)
        ans=min(ans,dp(l,i)+dp(i+1,r));
    ans+=sum[r]-sum[l-1];
    return ans;
}
int32_t main() 
{
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        sum[i]=sum[i-1]+arr[i];
    }
    memset(cache,-1,sizeof(cache));
    cout<<dp(1,n);
}


Measured memory_bytes: 4940
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define rep(i,n) for(i=0;i<n;i++)

int in(void){
	int i;
	scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;
	scanf("%lld",&i);
	return i;
}
int cmp(const void *a,const void *b){
	return *(long long *)a-*(long long *)b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long max(long long a,long long b){
	return a>b?a:b;
}

int main(void){
	int i;
	char o[50],e[50];
	scanf("%s %s",o,e);
	for(i=0;i<strlen(e);i++){
		printf("%c%c",o[i],e[i]);
	}
	if(strlen(o)!=strlen(e))
		printf("%c",o[i]);
	puts("");
	return 0;
}

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

long long func(long long h){
    if (h == 1) {
        return 1;
    }
    return func(h/2) * 2 + 1;
}

int main() 
{
    long long H;
    cin >> H;
    cout << func(H) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long MX=1e18;
const long long MD=1e9+7;
const int N=1e5+5;
long long n,a[100005],b[100005],c[100005],dp[100005][5];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i];
    dp[0][0]=a[0],dp[0][1]=b[0],dp[0][2]=c[0];
    for(int i=1;i<n;i++)
    {
        dp[i][0]+=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]+=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]+=max(dp[i-1][0],dp[i-1][1])+c[i];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}


Measured memory_bytes: 6528
/** "Ever tried.
         Ever failed.
               No matter.
                   Try Again.
                        Fail again.
                             Fail better.**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define pb push_back
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define Unique(n)        (n).erase(unique(s(n)), (n).end())
#define NumofDigits(n)   ((long long)log10(n)+1)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-9;
const int MOD = 1e9+7;
/*
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll fastpow(ll b, ll p)
{if(!p)return 1;ll ret = fastpow(b, p >> 1);ret *= ret;if(p&1)ret*= b;return ret;}
int dx[] = {- 1, 0, 0, 1, 0 };
int dy[] = { 0,- 1, 1, 0, 0 };*/
void File()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
int arr[105];
int main()
{
    ios_base::sync_with_stdio(0);
    int n,sum=0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    int m1 = sum / n;
    int m2 = sum / n + 1;
    int ans = 0;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        ans += (arr[i]-m1) * (arr[i]-m1);
        res += (arr[i]-m2) * (arr[i]-m2);
    }
    cout << min(ans, res);
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define asll unsigned long long
#define ll long long //20190711
#define pii pair<int,int>
#define st first
#define nd second
#define jn <<" "<< 			//20190830
#define ml <<endl; 			//20190831->20190903
#define co cout<<           //20190903
asll M=1e9+7;				//20190518->20190821
int h,w,k;						//20190831
int cm[7][7];
vector<bool> vb1,vb2;
bool skh[7],skw[7];
string si;

vector<bool> tobin(int n,int hw){
	vector<bool> r1;
	for(int i=0;i<hw;i++){
		r1.push_back(n%2);
		n=n/2;
	}
	return r1;
}

string bts(vector<bool> v){
	string ret="";
	for(int i=0;i<v.size();i++){
		if(v[i]){
			ret+="1";
		}
		else{
			ret+="0";
		}
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	srand(time(0));			//20190709
	cin>>h>>w>>k;
	for(int i=0;i<h;i++){
		cin>>si;
		for(int j=0;j<w;j++){
			if(si[j]=='.'){
				cm[i][j]=0;
			}
			else{
				//co "masuk sini" ml
				cm[i][j]=1;
			}
		}
	}
	
	/*
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			co cm[i][j];
		}
		co "" ml
	}
	*/
	
	int jml=0,bykcr=0;
	int putaran=0;
	for(int i=0;i<pow(2,h);i++){
		for(int j=0;j<pow(2,w);j++){
			//co "putaran" jn putaran jn i jn j ml
			vb1=tobin(i,h);
			vb2=tobin(j,w);
			for(int m=0;m<vb1.size();m++){
				skh[m]=vb1[m];
			}
			for(int m=0;m<vb2.size();m++){
				skw[m]=vb2[m];
			}
			jml=0;
			for(int m=0;m<h;m++){
				for(int l=0;l<w;l++){
					if(skh[m]==0 && skw[l]==0){
						jml+=cm[m][l];
						//co "m,l" jn m jn l ml
					}
				}
			}
			//co "" ml
			//co "k" jn k ml
			if(jml==k){
				//co "jml,i,j " jn jml jn bts(vb1) jn bts(vb2) ml
				bykcr++;
			}
			putaran++;
		}
	}
	cout<<bykcr<<endl;
}



Measured memory_bytes: 3944
/* Coached by rainboy */
#include <stdio.h>

int min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	int a, b, c, d, e, f, x, y, i, j, k, l, p_, p, q_, q;

	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
	p_ = 0, q_ = a * 100;
	for (i = 0; i * a * 100 <= f; i++)
		for (j = 0; (x = i * a + j * b) * 100 <= f; j++)
			for (k = 0; (y = min(f - (x * 100 + k * c), x * e - k * c)) >= 0; k++) {
				l = y / d;
				p = k * c + l * d;
				q = x * 100 + p;
				if (q == 0)
					continue;
				if (p_ * q < p * q_) {
					p_ = p;
					q_ = q;
				}
			}
	printf("%d %d\n", q_, p_);
	return 0;
}


Measured memory_bytes: 128
<?php
// Array - Finding Missing Cards
$card_num = trim(fgets(STDIN));
$suit_type = array("S","H","C","D");
// ?????????
for($i = 0; $i < count($suit_type); $i++){
    $cards[$i] = array_fill(1,13,0);
}
// cards?????¶???????¨????
for($i = 0; $i < $card_num; $i++){
    $trump = explode(" ",trim(fgets(STDIN)));
    $suit = array_search($trump[0],$suit_type); // S:0 H:1 C:2 D:3?????????
    $rank = $trump[1];
    $cards[$suit][$rank] = 1;
}
// ??????
for($i = 0; $i < 4; $i++){
    for($j = 1; $j <= 13; $j++){
        if($cards[$i][$j] === 0){
            echo $suit_type[$i]." ".$j."\n";
        }
    }
}

Measured memory_bytes: 15436
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int x,a,b;
    scanf("%d%d%d",&x,&a,&b);
    if(abs(a-x)<abs(b-x)) printf("A\n");
    else printf("B\n");
    return 0;
}



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

int main() 
{int n,d,t;
	cin >> n >> d;
	d=(2*d)+1;
	if(n%d==0){
		t=n/d;
	}else{
		t=(n/d)+1;
	}
	cout <<t;
    return 0; 
} 



Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int              { return readIntArray()[0] }
func readInt2() (int, int)      { a := readIntArray(); return a[0], a[1] }
func readInt3() (int, int, int) { a := readIntArray(); return a[0], a[1], a[2] }
func readIntArray() []int {
        a := make([]int, 0, 1000)
        sc.Scan()
        for _, v := range strings.Split(sc.Text(), " ") {
                vv, _ := strconv.Atoi(v)
                a = append(a, vv)
        }
        return a
}
func readString() string        { return readStringArray()[0] }
func readStringArray() []string { sc.Scan(); return strings.Split(sc.Text(), " ") }

func main() {
        var n int
        fmt.Scan(&n)
        cnt := 1
        for i := 0; i < n; i++ {
                var a int
                fmt.Scan(&a)
                if a == cnt {
                        cnt++
                }
        }
        if cnt == 1 {
                fmt.Println(-1)
        } else {
                fmt.Println(n - cnt + 1)
        }
}

Measured memory_bytes: 5504
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	string s;
	cin>>s;
	int n = s.size();
	int res = n;
	rep(i, n-1){
		if(s[i]!=s[i+1]){
			res = min(res, max(n-i-1, i+1));
		}
	}
	cout<<res<<endl;

	return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  vector<string> sm(N);
  vector<int> time(N);
  for (int i=0; i<N; i++) {
    cin >> sm.at(i) >> time.at(i);
  }
  
  string X;
  cin >> X;
  
  int asleep = 0;
  for (int i=0; i<N; i++) {
    if (sm.at(i) == X) {
      asleep = i;
      break;
    }
  }
  
  int ans = 0;
  for (int i=1+asleep; i<N; i++) {
    ans += time.at(i);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, length) for (int var = (begin); i < (length); i++)
#define RFOR(var, length, end) for (int var = (length) - 1; i >= (end); i--)
#define REP(var, length) FOR(var, 0, length)
#define RREP(var, length) RFOR(var, length, 0)
#define SORT(vector) sort(vector.begin(), vector.end())

const ll MOD = 1e9 + 7;

struct UnionFind {
    vector<int> par;
    vector<int> num;

    UnionFind(int n) : par(n), num(n, 1) {
      REP(i, n) par[i] = i;
    }

    int root(int x) {
      return par[x] == x ? x : par[x] = root(par[x]);
    }

    bool same(int x, int y) {
      return root(x) == root(y);
    }

    void unite(int x, int y) {
      x = root(x);
      y = root(y);

      if (x == y) return;

      par[x] = y;
      num[y] += num[x];
    }

    int size(int x) {
      return num[root(x)];
    }
};

void solve(istream& cin, ostream& cout) {
  int n, m;
  cin >> n >> m;

  vector<int> a(m), b(m);
  vector<ll> ans(m);

  REP(i, m) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }

  UnionFind uf(n);

  ans[m - 1] = (ll) n * (n - 1) / 2;

  RREP(i, m - 1) {
    if (!uf.same(a[i + 1], b[i + 1])) {
      ans[i] = ans[i + 1] - (ll) uf.size(a[i + 1]) * uf.size(b[i + 1]);
    } else {
      ans[i] = ans[i + 1];
    }
    uf.unite(a[i + 1], b[i + 1]);
  }

  REP(i, m) {
    cout << ans[i] << endl;
  }
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif


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

using namespace std;

#define FOR(i,s,e) for(int i=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp make_pair
#define mt make_tuple
#define t0(t) get<0>((t))
#define t1(t) get<1>((t))
#define t2(t) get<2>((t))

typedef long long ll;

int main() {
  int kk, s;
  fscanf(stdin, "%d%d ", &kk, &s);
  int l = max(s-kk,0), r = min(s, kk*2);
  int res = 0;
  FOR(i,l,r+1) REP(j,i+1)
    if (j <= kk && (i-j) <= kk) res++;
  fprintf(stdout, "%d\n", res);
  return 0;
}


Measured memory_bytes: 256
class Combi
  def initialize(max_n, mod = 10**9+7)
      @mod = mod
      @max_n = max_n
 
      @fac = Array.new(@max_n+1)
      @inv = Array.new(@max_n+1)
      @finv = Array.new(@max_n+1)
 
      @fac[0] = @fac[1] = 1
      @finv[0] = @finv[1] = 1
      @inv[1] = 1
      2.upto(@max_n) do |i|
          @fac[i] = @fac[i-1] * i % @mod
          @inv[i] = @mod - @inv[@mod%i] * (@mod/i) % @mod
          @finv[i] = @finv[i-1] * @inv[i] % @mod
      end
  end
 
  def nCk(n,k)
      @fac[n] * @finv[n - k] * @finv[k] % @mod
  end
end
 
x,y=gets.chomp.split.map(&:to_i)
 
if((2*x-y)%3!=0)
  puts 0
  exit
end
 
s=(2*x-y)/3;
 
if s<0
  puts 0
  exit
end
 
 
t=x-2*s
 
if(s<0 || t < 0)
  puts 0
  exit
end
 
 
combi = Combi.new(1000000)
 
puts combi.nCk(s+t,t)

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

using namespace std;

typedef long long ll;

const int MOD = 1000000007;
const int MAXN = 51;

int N;
ll K;
vector<vector<int>> A;

int add(int a, int b) {
  return (a + b) % MOD;
}
int mul(int a, int b) {
  return (ll(a) * ll(b)) % MOD;
}
vector<vector<int>> matmul(vector<vector<int>> a, vector<vector<int>> b, int n) {
  vector<vector<int>> ans(n, vector<int> (n));
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < n; ++j) {
      for(int k = 0; k < n; ++k) {
        ans[i][j] = add(ans[i][j], mul(a[i][k], b[k][j]));
      }
    }
  }
  return ans;
}
vector<vector<int>> matpow(vector<vector<int>> a, int n, ll k) {
  if(k == 1) return a;
  if(k % 2 == 0) {
    return matpow(matmul(a, a, n), n, k / 2);
  }
  return matmul(a, matpow(a, n, k - 1), n);
}

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

  cin >> N >> K;
  A = vector<vector<int>> (N, vector<int> (N));
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
      cin >> A[i][j];
    }
  }
  A = matpow(A, N, K);
  int ans = 0;
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
      ans = add(ans, A[i][j]);
    }
  }
  cout << ans <<"\n";
  return 0;
}

Measured memory_bytes: 6192
(*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*)

open System;

let n = int(Console.ReadLine());
let s = Console.ReadLine();

let rec ans i =
    if i + 1 >= n then 1
    else if s.[i] = s.[i+1] then ans (i+1)
    else ans (i+1) + 1

Console.WriteLine(ans 0);

Measured memory_bytes: 14420
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 101010;
const int M = 1e9+7;
int n;

ll ksm(ll a,ll b)
{
    ll res = 1;
    while (b)
    {
        if(b&1) res = (res*a)%M;
        a = (a*a)%M;
        b /= 2;
    }
    return res%M;
}

ll inv[maxn];
void getinv()
{
    inv[1] = 1;
    for(int i = 2; i < maxn; i++)
        inv[i] = (M-M/i)*inv[M%i]%M;
}

ll a[maxn];

ll b[maxn];

int main()
{
    getinv();
    cin>>n;
    ll res = 1;
    for(int i = 1; i < n; i++) 
    {
        res = (res*i)%M;
    }
    for(int i = 1; i <= n; i++) 
    {   
        cin>>a[i];
    }
    b[1] = res;
    for(int i = 2; i < n; i++) 
    {
        b[i] = (b[i-1]+(res*inv[i]%M))%M;
    }
    ll ans = 0;
    for(int i = 1; i < n; i++) 
    {   
        ans = (ans + (a[i+1]-a[i])*b[i])%M;
    }
    cout<<ans<<endl;
    return 0;
}

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

console.log(main());
function main(){
  n = o.a();
  xy = o.m(n);
  if(n === 2)return solve2(xy);
  for(var i = 0; i < n; i++)for(var j = i+1; j < n; j++){
    if(solve3(xy[i][0],xy[i][1],xy[j][0],xy[j][1])){
      ans = r;
    }
  }
  for(var i = 0; i < n; i++)for(var j = i+1; j < n; j++)for(var k = j+1; k < n; k++){
    if(solve(xy[i][0],xy[i][1],xy[j][0],xy[j][1],xy[k][0],xy[k][1])){
      ans = r;
    }
  }
  return ans;
}

function solve(x1,y1,x2,y2,x3,y3){
  var a = x1-x2, b = y1-y2, c = x2-x3, d = y2-y3;
  var k = 2*(a*d-b*c);
  if(k === 0){//一直線上
    return;
  }
  var v1 = x1*x1+y1*y1, v2 = x2*x2+y2*y2, v3 = x3*x3+y3*y3;
  k = 1/k;
  rx = k*(d*(v1-v2)-b*(v2-v3));
  ry = k*(a*(v2-v3)-c*(v1-v2));
  var dx = x1-rx, dy = y1-ry;
  r = Math.sqrt(dx*dx+dy*dy);
  return f();
}

function f(){
  if(ans < r)return;
  for(var i = 0; i < n; i++){
    var dx = xy[i][0]-rx, dy = xy[i][1]-ry;
    var rr = Math.sqrt(dx*dx+dy*dy);
    if(r < rr*e)return;
  }
  return 1;
}

function solve3(x1,y1,x2,y2){
  var dx = x1-x2, dy = y1-y2;
  rx = (x1+x2)/2, ry = (y1+y2)/2;
  r = Math.sqrt(dx*dx+dy*dy)/2;
  return f();
}

function solve2(x){
  var dx = x[0][0]-x[1][0], dy = x[0][1]-x[1][1];
  return Math.sqrt(dx*dx+dy*dy)/2;
}

Measured memory_bytes: 10092
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>
#include <cctype>
#include <climits>
#include <list>
#include <queue>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int N, bus_capacity, K; cin>>N>>bus_capacity>>K;
  vector<double> arive_times(N);
  for(int i=0; i<N; i++) {
    cin>>arive_times[i];
  }
  sort(arive_times.begin(), arive_times.end());

  int bus = 0, passenger = 0, limit = -1;
  for(int i=0; i<N; i++) {
    if(arive_times[i] > limit || passenger + 1 > bus_capacity) {
      // cout << "arive_times:" << arive_times[i] << " no:" << i << endl;
      bus++;
      passenger = 0;
      limit = arive_times[i] + K;
    }
    passenger++;
  }
  cout << bus << endl;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<ll,ll> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
 
	cin.tie(0); ios_base::sync_with_stdio(false);
	
	int h,w;
	cin >>h >>w;
	vector<string> ba(h);
	rep(i, h) cin >>ba[i];
	
	const int dr[]={0,1,0,-1,0};
	const int inf = 9999999;
	vector<vector<int> > dd(h, vector<int>(w, inf));
	queue< pii > que;
	que.push(pii( 0, 0)); dd[0][0]=0;
	while(!que.empty()){
		int cy,cx; tie(cy,cx) = que.front();
		que.pop();
		rep(i,4){
			int ny=cy+dr[i], nx=cx+dr[i^1];
			if(ny<0 || ny>=h || nx<0 || nx>=w) continue;
			if(dd[ny][nx] == inf && ba[ny][nx] =='.'){
				que.push( pii(ny, nx) );
				dd[ny][nx] = dd[cy][cx] + 1;
			}
		}
	}

	//for(auto xl: dd){for(auto x :xl) printf("%2d ",x); puts("");}
	int blk=0;
	rep(i, h) rep(j, w) blk += ba[i][j]=='#';
	if(dd[h-1][w-1] == inf) puts("-1");
	else cout << h*w - blk - dd[h-1][w-1] -1 <<"\n";
	return 0;
}


Measured memory_bytes: 256
dur=int(input())
c=list(map(int,input().split()))
d=[0]*26
r=3
for i in range(dur):
  t=0
  s=list(map(int,input().split()))
  m=-1<<64
  for j in range(26):
    alt=s[j]+r*c[j]*(i+1-d[j])+sum([-r*c[k]*(i+1-d[k]) for k in range(26)])
    if alt>m:
      m=alt
      t=j
  print(t+1)
  d[t]=i+1


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

#define ll long long;
#define pi acos(-1);

int main(){
   int a,b;
   cin>>a>>b;
   while (b)
   {
      a = a % b;
      swap(a,b);
   }
   
    cout<<a<<endl;
   

   return 0;
}


Measured memory_bytes: 3100
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		N = N%10;
      
		if(N==2||N==4||N==5||N==7||N==9){
			System.out.println("hon");
        }else if(N==0||N==1||N==6||N==8){
			System.out.println("pon");
        }else{
			System.out.println("bon");
        }
    }
}


Measured memory_bytes: 35632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,ans;
  ans=0;
  cin>>n;
  vector<int> vec(n);
  for(int i=0; i<n; i++){
    cin>>vec.at(i);
  }
  for(int i=0; i<n-1; i++){
    if(i+1==vec.at(i)){
      ans=ans+1;
      vec.at(i+1)=vec.at(i);
    }
  }
  if(vec.at(n-1)==n){
    ans++;
  }
  cout<<ans;
}

Measured memory_bytes: 640
//
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

int main(){

    set<char>S;
    string s;
    cin >> s;
    rep(i, s.size())S.insert(s[i]);
    if(S.size() == 1)cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#pragma warning(disable : 4996)
using namespace std;
int N, T, a[200009];
int main() {
	scanf("%d %d", &N, &T);
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	int ret = 0;
	for (int i = 0; i < N; i++) {
		if (i + 1 == N || a[i + 1] - a[i] >= T) ret += T;
		else ret += a[i + 1] - a[i];
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 1024
import sys
while True:
    sells=[]
    for i in range(5):
        s1,s2=[int(j) for j in input().split(" ")]
        if s1==0 and s2==0:
            sys.exit()
        sells.append(s1+s2)
    print(chr(ord('A')+sells.index(max(sells))),max(sells))



Measured memory_bytes: 5608
#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>;

template <class _T> inline bool chmax (_T& a,_T b){if(a<b){a=b;return true;}return false;}
template <class _T> inline bool chmin (_T& a,_T b){if(a>b){a=b;return true;}return false;}

const long long INF = 1LL << 60;

ll chabs(ll a,ll b){
	ll c = a;
	c = min(a,abs(a-b));
	return c;
}
int main(void){
	ll n,k;cin >> n >> k;
	ll ans;
	ans = min(n%k,k-(n%k));
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	int n;
	float x1,y1,x2,y2,x3,y3,x4,y4,s1,s2;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
		s1=(y2-y1)/(x2-x1);
		s2=(y4-y3)/(x4-x3);
		if(s1==s2){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;	
		}
	}
}


Measured memory_bytes: 1224
n=int(input())
change_1_9=[]
a=n//100
b=(n-100*a)//10
c=n-100*a-10*b


if (a==9):
  change_1_9.append(1)
else:
  change_1_9.append(9)
if (b==9):
  change_1_9.append(1)
else:
  change_1_9.append(9)
if (c==9):
  change_1_9.append(1)
else:
  change_1_9.append(9)
print(''.join(map(str,change_1_9)))

Measured memory_bytes: 3064
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define MAX(a,b) (a>b?a:b)
using namespace std;

int main(){
  vector<string> S;
  int scnt = 0;
  string SP, T;
  bool isRestore=false;
  cin >> SP >> T;
  rep(i,SP.size()){
    if(SP[i]==T[0]||SP[i]=='?'){
      bool flag = true;
      rep(j,T.size()){
	if(SP[i+j] != '?' && SP[i+j]  != T[j]){
	  flag = false;
	  break;
	}
      }
      if(flag){
	isRestore = true;
	S.push_back(SP);
	rep(k,SP.size()){
	  if((k<i || k>=i+T.size()) && S[scnt][k] == '?' ) {
	    S[scnt][k] = 'a';
	  }
	  else if(k>=i && k<i+T.size()){
	    S[scnt][k] = T[k-i];
	  }
	}
	scnt++;
      }
    }
  }	

  //sort(S.begin(), S.end(),std::greater<string>());
  sort(S.begin(), S.end());
  if(isRestore) cout << S[0] << endl;
  else cout << "UNRESTORABLE" << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
#define NUM ((long long)1000000007)
//#define int long long

using namespace std;

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

    int n, m;
    cin >> n;
    unordered_map<string, int> v1;
    for (size_t i = 0; i < n; i++)
    {
        string tmp;
        cin >> tmp;
        auto iter1 = v1.find(tmp);
        if (iter1 != v1.end())
        {
            iter1->second += 1;
        }
        else
        {
            v1.insert({ tmp,1 });
        }
    }
    cin >> m;
    unordered_map<string, int> v2;
    for (size_t i = 0; i < m; i++)
    {
        string tmp;
        cin >> tmp;
        auto iter1 = v2.find(tmp);
        if (iter1 != v2.end())
        {
            iter1->second += 1;
        }
        else
        {
            v2.insert({ tmp,1 });
        }
    }
    vector<int> ans;
    for (auto& i : v1)
    {
        auto tmp = v2.find(i.first);
        if (tmp != v2.end())
        {
            ans.emplace_back(i.second - tmp->second);
        }
        else
        {
            ans.emplace_back(i.second);
        }
    }
    auto a = *max_element(ans.begin(), ans.end());

    if (a <= 0)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << a << endl;
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        //input
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        boolean[] b_ar = new boolean[N];

        for(int i=0;i<N;i++){
        	b_ar[i] = IsRightTriangle(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }

        //output
        for(boolean b:b_ar){
        	if   (b) { System.out.println("YES");}
        	else     { System.out.println("NO"); }
        }
    }

    private static boolean IsRightTriangle(int a,int b,int c){
    	if( Math.pow((double)a,2) + Math.pow((double)b,2) == Math.pow((double)c,2) ||
            Math.pow((double)b,2) + Math.pow((double)c,2) == Math.pow((double)a,2) ||
            Math.pow((double)c,2) + Math.pow((double)a,2) == Math.pow((double)b,2)    ){
    		return true;
    	}else {
    		return false;
    	}
    }
}

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

int main() {
  int x;
  cin>>x;
  int ans=0;
  int a=x/500;
  ans+=a*1000;
  x-=a*500;
  a=x/5;
  ans+=a*5;
  cout<<ans<<endl;
}


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

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


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

#define int long long
const int maxn = 1e5 + 10;
int n, M = 0, C;
int par[maxn];
vector <pair <int, int>> Q1;
set <int> she;

int root(int v){
	if (par[v] < 0)
		return v;
	return par[v] = root(par[v]);
}

void merge(int v, int u){
	v = root(v);
	u = root(u);
	if (v == u)
		return;
	M ++;
	if (par[v] < par[u])
		swap(v, u);
	par[u] += par[v];
	par[v] = u;
	C --;
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m, q;
	cin >> n >> m >> q;
	C = n;
	fill(par, par + n, -1);
	while (q --){
		int a, b, c;
		cin >> a >> b >> c;
		if (c == 0)
			merge(a, b);
		else{
			Q1.push_back({a, b});
		}
	}
	if (m < M){
		cout << "No";
		return 0;
	}
	if (C == 1 || C == 2){
		if (Q1.size()){
			cout << "No";
			return 0;
		}
		if (C == 1){
			if (m != M){
				cout << "No";
				return 0;
			}
			else{
				cout << "Yes";
				return 0;
			}
		}
		else{
			int x = *(min_element(par, par + n)), y = *(max_element(par, par + n));
			if (M + x * y < m){
				cout << "No";
				return 0;
			}
			else{
				cout << "Yes";
				return 0;
			}
		}
	}
	for (auto P: Q1){
		int v = P.first, u = P.second;
		if (root(v) == root(u)){
			cout << "No";
			return 0;
		}
		she.insert(root(v));
		she.insert(root(u));
	}
	if (M + she.size() > m){
		cout << "No";
		return 0;
	}
	if (m > M + C * (C - 1) / 2){
		cout << "No";
		return 0;
	}
	cout << "Yes";
}


Measured memory_bytes: 7280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

int main(){
  ll n;
  cin >> n;
  vector<vector<ll>> vec(n,vector<ll>(n));
  rep(i,n){
    rep(j,n){
      cin >> vec[i][j];
    }
  }
  vector<ll> arr(n,0);
  arr[0] = 1;
  priority_queue<pair<ll,ll>> pq;
  rep(i,n){
    if(vec[0][i] != -1){
      pq.push(make_pair(-vec[0][i],i));
    }
  }
  pair<ll,ll> pa;
  ll ans = 0;
  while(!pq.empty()){
    pa = pq.top();
    pq.pop();
    if(arr[pa.second] == 0){
      arr[pa.second] = 1;
      ans -= pa.first;
      rep(i,n){
        if(vec[pa.second][i] != -1){
          pq.push(make_pair(-vec[pa.second][i],i));
        }
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3308
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

int main(int argc, const char * argv[]) {
    int N = 0;
    cin >> N;

    vector<int> As(N+1, 0);
    for(int i = 0; i < N+1; i++) {
        cin >> As[i];
    }

    vector<int> Bs(N, 0); // max monster beaten by a yuusha i
    for(int i = 0; i < N; i++) {
        cin >> Bs[i];
    }

    uint64_t total_beats = 0;
    for(int i = 0; i < N; i++) {
        // yuusha i beates monsters in city i
        {
            int beat_i = 0;
            if(Bs[i] <= As[i]) {
                beat_i = Bs[i];
            } else {// Bs[i] > As[i]
                beat_i = As[i];
            }
            Bs[i] -= beat_i;
            As[i] -= beat_i;
            total_beats += (uint64_t) beat_i;
        }
        // yuusha i beates monsters in city i+1
        {
            int beat_i2 = 0;
            if(Bs[i] <= As[i+1]) {
                beat_i2 = Bs[i];
            } else {// Bs[i] > As[i]
                beat_i2 = As[i+1];
            }
            Bs[i]   -= beat_i2;
            As[i+1] -= beat_i2;
            total_beats += (uint64_t) beat_i2;
        }
    }
    cout << total_beats << endl;
    return 0;
}

/**
 cheat sheet

 vector<int> v{ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
 sort(v.begin(), v.end());
 => 0 1 2 3 4 5 6 7 8 9

 vector<int> v{ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
 sort(v.begin(), v.end(), greater<int>());
 => 9 8 7 6 5 4 3 2 1 0

 struct A { int x, y; };
 bool comp(A i1, A i2) { return (i1.y < i2.y); }
 vector<A> v { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
 sort(v.begin(), v.end(), comp);
 => [1, 9] [2, 4] [4, 7] [6, 8]

 */


Measured memory_bytes: 1024
def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)


Measured memory_bytes: 117284
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
N = int(input())
for p in primes(10**5+100):
    if N<=p:
        print(p)
        break


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

int main(void)
{
	int n, T, err, i, min;
	int *c, *t;
	err = scanf("%d%d", &n, &T);
	if (err!=2 || (n<1||n>100) || (T<1||T>1000)) exit(1);
	c = (int *)malloc(sizeof(int)*n);
	t = (int *)malloc(sizeof(int)*n);
	for (int i = 0; i < n; ++i)
	{
		err = scanf("%d%d", &c[i], &t[i]);
		if (err!=2 || (c[i]<1||c[i]>1000) || (t[i]<1||t[i]>1000)) exit(1);
	}

	for (int i = 0; i < n; ++i)
	{
		if (t[i] > T) c[i] = INT_MAX;
	}
	min = c[0];
	for (int i = 1; i <= n-1; ++i)
	{
		if (c[i] < min) min = c[i];
	}
	if (min < INT_MAX)
	{
		printf("%d\n", min);
	}else
	{
		printf("TLE\n");
	}
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  int cnt = 0;
  bool x = true;
  
  if(s.at(1) == 'S') {
    for(int i = 0; i < 3; i++) {
      if(s.at(i) == 'R') {
        cout << 1 << endl;
        x = false;
        break;
      }
    }
  }
  
  else if(s.at(0) == 'S' || s.at(2) == 'S') {
     for(int i = 0; i < 3; i++) {
      if(s.at(i) == 'R') {
        cnt++;
        x = false;
      }
    }
    cout << cnt << endl;
  }
  
  else {
    x = false;
    for(int i = 0; i < 3; i++) {
      if(s.at(i) == 'R') cnt++;
    }
    cout << cnt << endl;
  }
  if(x) cout << 0 << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<int,int>a,pair<int,int>b)
{
	return a.second<b.second;
}
int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>> v(n);
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		v.push_back(make_pair(i,x));
	}
	sort(v.begin(), v.end(),comp);
	for(int i=n;i<n+n;i++)
		cout<<v[i].first<<" ";
	return 0;
}

Measured memory_bytes: 2416
#include <cstdio>
#include <cstring>
const int MAXS = 15;
char S[MAXS];
char T[MAXS];
int N;

int main() {
  scanf(" %s", S);
  scanf(" %s", T);
  N = strlen(S);
  T[N] = '\0';
  puts((strcmp(S, T) == 0) ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf 1000000000
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define f first
#define s second

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


	ll n,W;
	cin>>n>>W;
	ll w[n+1],v[n+1];
	ll V=0;
	for(ll i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
		V=max(V,v[i]);
	}
	V*=n;
	ll dp[n+1][V+1];
	dp[0][0]=0;
	for(ll i=1;i<=n;i++)
		dp[i][0]=0;
	for(ll i=1;i<=V;i++)
		dp[0][i]=inf;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=V;j++)
		{
			if(j<v[i])
			{	
				dp[i][j]=dp[i-1][j];
			}
			else
				dp[i][j]=min(dp[i-1][j],w[i]+dp[i-1][j-v[i]]);

		}
	}

	ll ans=0;
	for(ll i=V;i>=0;i--)
	{
		if(dp[n][i]<=W)
		{
			ans=i;
			break;
		}
	}
	cout<<ans<<'\n';
}	


Measured memory_bytes: 79232
while 1:
    try:
        xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = map(float, input().split())
        if max(xa1, xb1) <= min(xa2, xb2) and max(ya1, yb1) <= min(ya2, yb2):
            print('YES')
        else:
            print('NO')

    except:
        break



Measured memory_bytes: 5576
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;


vector<int> p;

bool is_p(int n){
	if(n<=1)return false;
	for(int i=2; i<=sqrt(n); i++){
		if(n%i==0)return false;
	}
	return true;
}
void make_p(){
	int i=2;
	while(1){
		if(is_p(i))p.push_back(i);
		i++;
		if(p.size()==10000)break;
	}
}



int main(){
	int m;
	make_p();
	while(1){
		long long int ans=0;
		cin>>m;
		if(m==0)break;
		for(int j=0; j<m; j++){
			ans+=p.at(j);
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1316
N = int(input())
X = [int(i) for i in input().split()]

mpow = 100*100*100*100*100

for P in range(100):
    temp = 0
    for Xi in X:
        temp += (Xi-P)*(Xi-P)
        if temp > mpow:
            break 
    if temp < mpow:
        mpow = temp

print(mpow)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

//a[i]=iが2017に似た数なら1、違ければ0 を考えると累積和になる

int main(){
   //エラトステネスのふるい
    int MAX = 101010;
    vector<int> is_prime(MAX,1);
    is_prime[0]=0;
    is_prime[1]=0;
    for(int i=2; i<MAX; i++){
        if(!is_prime[i]) continue;
        for(int j=i*2; j<MAX; j+=i) is_prime[j]=0;
    }

    //2017に似た数かどうか
    vector<int> a(MAX,0);
    for(int i=0; i<MAX; i++){
        if(i % 2 == 0) continue; //偶数は与えられないし絶対素数じゃない
        if(is_prime[i] && is_prime[(i+1)/2]) a[i]=1;
    }

    //l<=x<=rで2017に似た数の総和はaの累積和を用いて高速に求められる
    vector<int> s(MAX+1,0);
    for(int i=0; i<MAX; i++) s[i+1] = s[i] + a[i];

    //クエリ処理
    int Q; 
    cin >> Q; //Q個のクエリが与えられる
    for(int q=0; q < Q; ++q){
        int l, r;
        cin >> l >> r;
        ++r; //今回のクエリではr自身も含むので+1する

        cout << s.at(r) - s.at(l) << endl;
    }
}

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

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

    if(s[k-1] == 'A') s[k-1] = 'a';
    else if(s[k-1] == 'B') s[k-1] = 'b';
    else if(s[k-1] == 'C') s[k-1] = 'c';

    cout << s << endl;
}

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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define CEVCOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define M map<int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>
int main(void) {

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

	int N;		cin >> N;
	string str;	cin >> str;
	V left(N);	left[0] = 0;	//i番目より左にいる西向きの数
	V right(N);	right[N - 1] = 0;	//i番目より右にいる東向きの数

	for(int i = 1 ; i < N ; i++){
	 	if(str[i - 1] == 'W')	left[i] = left[i - 1] + 1;
		else		left[i] = left[i - 1];
	}

	for(int i = N - 2 ; 0 <= i ; i--){
	 	if(str[i + 1] == 'E')	right[i] = right[i + 1] + 1;
		else		right[i] = right[i + 1];
	}

	int ans = INF;
	for(int i = 0 ; i < N ; i++)
	 	ans = min(ans , right[i] + left[i]);
    
	SCOUT(ans) << endl;

	return 0;
}


Measured memory_bytes: 3092
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e9+7;
const ll inf=1e18;
const ll ms=1e7+2;
fast;
ll ans;
ll n,m,q;
void solve()
{
   string s;cin>>s;
   ll yy=(s[0]-'0')*10+s[1]-'0';
   ll mm=(s[2]-'0')*10+s[3]-'0';
   if(mm==0)
   {
       if(yy==0||yy>12)
        {cout<<"NA";return;}
        else
       {
           cout<<"MMYY";return;
       }
   }
   if(yy==0)
   {
       if(mm==0||mm>12)
       {cout<<"NA";return;}
       else
       {
           cout<<"YYMM";return;
       }
   }
   if(yy<13&&mm<13)
   {
       cout<<"AMBIGUOUS";return;
   }
   if(yy>12&&mm>12)
   {
       cout<<"NA";return;
   }
   if(mm<13)
   cout<<"YYMM"<<endl;
   else
    cout<<"MMYY"<<endl;
}

int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
   // int t;cin>>t;while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());

		// int[] A = Arrays.stream(sc.nextLine().split("
		// ")).mapToInt(Integer::parseInt).toArray();

		int[] A = new int[N];

		for (int k = 0; k < N; k++) {
			A[k] = Integer.parseInt(sc.next());
		}

		int tmp;
		int minj;
		int count = 0;
		
		for (int i=0; i<N; i++) {
			minj = i;
			for (int j=i; j<N; j++) {
				if (A[j] < A[minj])
					minj = j;
			}
			if (A[minj] != A[i])
				count++;
			tmp = A[minj];
			A[minj] = A[i];
			A[i] = tmp;
		}
			
		out_put(A);

		System.out.println(count);

		sc.close();
	}

	private static void out_put(int array[]) {

		System.out.printf("%d", array[0]);

		for (int i = 1; i < array.length; i++) {
			System.out.printf(" %d", array[i]);
		}
		System.out.printf("\n");
	}
}



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

int main() {
  int N,M;
  cin>>N>>M;
  vector<vector<int>> p(M,vector<int>(2));

  for(int i=0;i<M;i++){
    int a;
    string b;
    cin>>a>>b;
    p[i][0]=a;
    if(b=="AC")p[i][1]=1;
    else p[i][1]=0 ;
  }
  vector<int> q(N);
  vector<int> w(N);

  int ans=0,pen=0;
  for(int i=0;i<M;i++){
    int x=p[i][0]-1,y=p[i][1];
    //cout<<x<<y<<endl;
    if(q[x]==0){
      if(y==0){
        w[x]++;
      }
      if(y==1){
        ans++;
        pen+= w[x];
        q[x]=1;
      }
    }
  }
  cout<<ans<<" "<<pen<<endl;
}


Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
ll H,W;
vector<string> S;
vector<ll> serch2(ll i,ll j);
vector<ll> serch1(ll i,ll j){
   //#
  //if(i>=H||j>=W)return 0;
  char c=S[i][j];
  //cout<<i<<","<<j<<endl;
  if(c=='#'){
    S[i][j]='_';
    vector<ll> ret{1,0};
    vector<ll> buf;
    if(i+1<H){
      buf = serch2(i+1,j);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(i>0){
      buf=serch2(i-1,j);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(j+1<W){
      buf=serch2(i,j+1);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(j>0){
      buf=serch2(i,j-1);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    return ret;
  }
  return vector<ll>{0,0};
}
vector<ll> serch2(ll i,ll j){
  //.
  //if(i>=H||j>=W)return 0;
  char c=S[i][j];
  if(c=='.'){
    S[i][j]='_';
    vector<ll> ret{0,1};
    vector<ll> buf;
    if(i+1<H){
      buf = serch1(i+1,j);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(i>0){
      buf=serch1(i-1,j);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(j+1<W){
      buf=serch1(i,j+1);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    if(j>0){
      buf=serch1(i,j-1);
      ret[0]+=buf[0];
      ret[1]+=buf[1];
    }
    return ret;
  }
  return vector<ll>{0,0};
}
int main(){
  //ll H,W;
  cin>>H>>W;
  for(int i=0;i<H;++i){
    string tmp;
    cin>>tmp;
    S.push_back(tmp);
  }
  ll num=0;
  for(int i=0;i<H;++i){
    for(int j=0;j<W;++j){
      vector<ll> tmp = serch1(i,j);
      num+=tmp[0]*tmp[1];
    }
  }
  cout<<num<<endl;
  return 0;
}

Measured memory_bytes: 40448
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll gcd(ll x,ll y){
  return y?gcd(y,x%y):x;
}
int main(){
  ll n,x;
  cin>>n>>x;
  ll z[n+1]={};
  for(int i=0;i<n;i++){
    cin>>z[i];
    z[i]-=x;
    z[i]=abs(z[i]);
  }
  ll m=z[0];
  for(int i=1;i<n;i++){
    m=gcd(m,z[i]);
  }
  cout<<m<<endl;
  /*ll l=1,r=1e9;
  while(r-l>1){
    ll m=(r+l)/2;
    bool flag=0;
    for(int i=0;i<n;i++){
      if(z[i]%m!=0){
        flag=1;
        break;
      }
    }
    cout<<r<<" "<<l<<endl;
    if(flag) r=m;
    else l=m;
  }
  cout<<l<<endl;*/

  return 0;
}


Measured memory_bytes: 1024
N,M=map(int, input().split())
AB=list(sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x :x[1]))
ans=1
A=[AB[0]]
for i in range(1,M):
    if AB[i][0]>=A[-1][1]:
        ans+=1
        A.append(AB[i])
print(ans)


Measured memory_bytes: 29848
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ll a, b , n,x;
    cin >> a >> b >> n;
    if(n  <  b)  x = n;
    else
    {
        x = b-1;

    }
    ll ans = floor((a*x)/b)-(a* floor(x/b));
    cout << ans <<"\n";
}

Measured memory_bytes: 3624