akhauriyash/Code-Regression huggingface dataset:
/*
If you want to shine like a sun, first burn like a sun.
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long int
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define v2i vector<vector<int>>
#define v2l vector<vector<ll>>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define vpi vector<ppi>
#define vpl vector<ppl>
#define all(x) x.begin(),x.end()
#define ii int,int 
#define ff first    
#define ss second
#define forn(i,a,b) for(int i=a;i<b;i++)
#define forr(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,m) for(auto i : m)
#define imx INT_MAX
#define imn INT_MIN
#define inf 9000000000000000000
#define minf -inf
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define sze size()
#define rvs reverse 
#define itr iterator 
#define pre cout<<fixed<<setprecision(10);
#define umap unordered_map
#define uset unordered_set
#define pi 3.141592653589793
#define MAXN 100005
#define test1(x) cout << #x " = " << x << endl;
#define test2(x,y) cout << #x " = " << x << " " << #y " = " << y << endl;
const ll infinity = 9e18;

/*
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MODM(a,b,md) ((a%md)*(b%md))%md
#define MODA(a,b,md) ((a%md)+(b%md))%md
#define ull unsigned long long int
*/

/*
bool compare(int a,int b) {return a > b;}
bool compare1(ppi a,ppi b) {return a.ff > b.ff;}
bool compare2(ppi a,ppi b) {return a.ss < b.ss;}
ll Npower(ll a,ll b) {ll product = 1; while(b){if(b&1){product = product*a;}a = a*a;b = b>>1;} return product;}
ll power(ll a,ll b,ll md) {ll product = 1; while(b){if(b&1){product = MODM(product,a,md);}a = MODM(a,a,md);b = b>>1;} return product%md;}
bool isprime(ll n){if(n < 2) return 0; ll i = 2; while(i*i <= n){if(n%i == 0) return 0; i++;} return 1;}
ll GCD(ll a,ll b) {return b==0 ? a:GCD(b,a%b);}
ll LCM(ll a,ll b) {return (a/GCD(a,b))*b; }
*/


int main()
{
    fast

/*
    #ifndef ONLINE_JUDGE
        freopen("input.txt",  "r",  stdin);
        freopen("output.txt", "w", stdout);
    #endif
//*/

        
    ll n;
    cin>>n;

    vl v(n);

    map<ll,ll> m;

    forn(i,0,n)
    {
        cin>>v[i];
        m[v[i]]++;
    }
        
    ll total = 0;

    forv(i,m)
    {
        total += ((i.ss)*(i.ss-1))/2;
    }    

    map<ll,ll> m1;

    forv(i,m)
    {
        m1[i.ff] = total - ((i.ss)*(i.ss-1))/2 + ((i.ss-1)*(i.ss-2))/2;
    }

    forv(i,v)
    {
        cout<<m1[i]<<endl;
    }








    return 0;
}       

Measured memory_bytes: 18944
S = input()

if S == "SUN":
  print(7)
elif S == "MON":
  print(6)
elif S == "TUE":
  print(5)
elif S == "WED":
  print(4)
elif S == "THU":
  print(3)
elif S == "FRI":
  print(2)
elif S == "SAT":
  print(1)

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

using namespace std;

int main(){
  int A,B,C;
  int X;
  cin>>A>>B>>C>>X;

  int ans=0;

  for(int a=0;a<=A;a++){
    for(int b=0;b<=B;b++){
      for(int c=0;c<=C;c++){
        if((500*a+100*b+50*c)==X) ans++;
      }
    }
  }

  cout <<ans <<endl;

  return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

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


int main() {
  bool is_prime[N+1];
  REP(i, N+1)
    is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int j = 4; j <= N; j += 2)
    is_prime[j] = false;
  for (int i = 3; i * i <= N;) {
    for (int j = i * 2; j <= N; j += i)
      is_prime[j] = false;
    i += 2;
    while (!is_prime[i])
      i += 2;
  }

  int count[N+1];
  count[0] = 0;
  FOR(i, 1, N+1) {
    count[i] = count[i-1] + (is_prime[i] && is_prime[(i+1)/2] ? 1 : 0);
  }

  int Q;
  cin >> Q;

  REP(i, Q) {
    int l, r;
    cin >> l >> r;
    cout << count[r] - count[l - 1] << endl;
  }

  return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};


int main(void){
    int M;
    cin >> M;
    cout << 48 - M << endl;
}


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

using namespace std;

#define vi vector<int>
#define all(v) v.begin(),v.end()
#define ll long long int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define D1(x) {cerr<<" [" <<#x<<": "<<x<<"]";cout << endl;}
#define D2(x) {cerr<<" [" <<#x<<": ";for(auto it:x)cerr<<it<< " ";cerr<<"] ";cout << endl;}

const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;

void solve(){
   int n;
   cin >> n;
   map<int,int> mp[2];
   int x;
   for(int i=0;i<n;i++){
     cin >> x;
     mp[i&1][x]++;		
   } 
   vector<pair<int,int>> v[2];
   for(int i = 0 ; i < 2 ; i ++ ){
	for(auto x:mp[i]){
	   v[i].push_back({x.second,x.first});
	}
	if(v[i].size()==1)v[i].push_back({0,-1});
    sort(v[i].rbegin(),v[i].rend());
    }
    int ans =0;
    for(int i=0;i<2;i++){
	for(int j=0;j<2;j++){
	    if(v[0][i].second!=v[1][j].second){
		ans = max(ans,v[0][i].first+v[1][j].first);
	    }	
	}
    }
    cout << n - ans;
   
}

int main() {
    IOS
	
        solve();
    cerr << endl << "[ Time : " << (float) clock() / CLOCKS_PER_SEC << " secs ]" << endl;

}
// integer overflow
// remember to clear visited array
// take input as vector<string> while using grid
// don't assign after modifying


Measured memory_bytes: 8920
#include<iostream>
using namespace std;
int main(){
  int n,m[7];
  double h;
  cin >> n;
  for(int i=0;i<7;i++) m[i] = 0;
  for(int i=0;i<n;i++){
    cin >> h;
    if(h<165.0) m[1]++;
    else if(h<170.0) m[2]++;
    else if(h<175.0) m[3]++;
    else if(h<180.0) m[4]++;
    else if(h<185.0) m[5]++;
    else m[6]++;
  }
    for(int i=1;i<7;i++){
      cout << i << ':';
      for(int j=0;j<m[i];j++) cout << '*';
      cout << endl;
    }
  return 0;
}

Measured memory_bytes: 1232
x, y = map(int, input().split())
f = False
for i in range(x+1):
    for j in range(x+1):
        if (y == (i*2 + j*4)):
            if (x == i + j):
                f = True
                break
    if f:
        break
if f:
    print("Yes")
else:
    print("No")            
            

Measured memory_bytes: 9180
N = int(input())
tasks = [list(map(int, input().split())) for _ in range(N)]
tasks.sort(key = lambda x: x[1])
now = 0
flag = True
for a, b in tasks:
    now += a
    if now > b:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 53728
fun main(arr: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }
    val cnt = mutableMapOf<Long, Int>()
    for(i in a) {
        val tmp = cnt[i]?:0
        cnt[i] = tmp + 1
    }
    val list = cnt.filter { it.value >= 2 }.keys.sortedByDescending { it }
    if(list.isEmpty()) {
        println(0)
        return
    }
    if(cnt[list[0]]!! >= 4) {
        println(list[0]*list[0])
    } else {
        println(list[0] * list[1])
    }
}


Measured memory_bytes: 59960
N = int(input())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare1 = dp[i-1] + abs(h[i]-h[i-1])
    compare2 = dp[i-2] + abs(h[i]-h[i-2])
    dp[i] = min(compare1, compare2)

print(dp[-1])


Measured memory_bytes: 13928
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

		var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];

			var amari = N % 1000;

			//答えの出力
			var ans = amari == 0 ? 0 : 1000 - amari;
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 28228
import itertools

N, D = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))

ans = 0
for x1, x2 in itertools.combinations(x, 2):
    d = sum((yi - zi)**2 for yi, zi in zip(x1, x2)) ** 0.5
    if d == int(d):
        ans += 1

print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

using namespace std;

int main(){
	int N,K;
	string S;
	cin >> N >> K;
	cin >> S;
	if(S[K-1] == 'A'){
		S[K-1] = 'a';
	}else if(S[K-1] == 'B'){
		S[K-1] = 'b';
	}else{
		S[K-1] = 'c';
	}
	
	cout << S << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>

int main()
{
	int ch;
	while(ch = getchar(), ch != EOF)
	{
		if(islower(ch))
		{
			putchar(toupper(ch));
		}
		else if(isupper(ch))
		{
			putchar(tolower(ch));
		}
		else
		{
			putchar(ch);
		}
	}
	return 0;
}


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

int main(){
    string s;
    cin>>s;
    int n=s.length(), ans=1;
    bool two=true;
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1]&&two){
            i++;
            if(i==n) break;
            two=false;
        }else{
            two=true;
        }
        ans++;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
char s[100005];
char t[100005];
map<long long,char> mp;
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",s);
	scanf("%s",t);
	long long l = (long long)n * (long long)m / (long long)__gcd(n,m);
	int c = 0;
	for(long long i = 0; i < l; i += (long long)l/n){
		mp[i] = s[c++];
	}
	c = 0;
	for(long long i = 0; i < l; i += (long long)l/m){
		if(mp.find(i) != mp.end()){
			if(mp[i] != t[c]){
				printf("-1\n");
				return 0;
			}
		}
		c++;
	}
	printf("%lld\n",l);
	return 0;
}

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

using namespace std;

int main(){
	int A, B, suma = 0;
	cin >> A >> B;
	suma = max(A,B);
	if(A >= B) {
		A--;
	}
	else {
		B--;
	}
	suma += max(A,B);
	cout << suma;
	return 0;
}

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

using namespace std;

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define rep(i, n) for(int i = 0; i < n; i++)
#define outl(x) cout<< (x) << '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

template<typename Tn> Tn gcd(Tn a, Tn b)
{
	return (b ? gcd(b, a % b) : a);
}

template<typename Tn> Tn lcm(Tn a, Tn b)
{
	return a / gcd(a, b) * b;
}

string IntToString(int number)
{
	stringstream ss;
	ss << number;
	return ss.str();
}

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

int main()
{
    int n, a, b;
    ci >> n >> a >> b;

    co << min(a, b) << ' ' << max(0, a + b - n) << en;
  
    return 0;
}









Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(){
	double x1,y1,x2, y2;
	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	printf("%lf\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int N = 2e5+5;

int n;
vector<int> al[N];

ii dfs(int u, int p) {
    ii cur = ii(u,-1);
    for (auto v : al[u]) if (v != p) {
        ii nxt = dfs(v, u);
        if (nxt.sc > cur.sc) cur = nxt;
    }
    cur.sc += 1;
    //cout << u << " " << cur.fi << " " << cur.sc << endl;
    return cur;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    FOR(i,1,n-1){
        int x, y; cin >> x >> y;
        al[x].pb(y);
        al[y].pb(x);
    } 

    int u = dfs(1,0).fi;
    cout << (dfs(u,0).sc % 3 == 1 ? "Second" : "First") << '\n';
}



Measured memory_bytes: 23680
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int read();
vector<int> c[200005];
int w[200005];

int fsp(int bs, int p) {
	int rt = 1;
	while (p) {
		if (p & 1) rt = 1ll * rt * bs % mod;
		bs = 1ll * bs * bs % mod, p >>= 1;
	}
	return rt;
}

int fac[200005], caf[200005];
void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = 1ll * i * fac[i - 1] % mod;
	caf[n] = fsp(fac[n], mod - 2);
	for (int i = n; i >= 1; --i) caf[i - 1] = 1ll * i * caf[i] % mod;
}

int main() { 
	int n = read(), X = read(), Y = read();
	init(n);
	for (int i = 1, tc, tw; i <= n; ++i) {
		tc = read(), tw = read();
		if (!c[tc].size()) w[tc] = tw;
		c[tc].push_back(tw), w[tc] = min(tw, w[tc]);
	}
	int mc1 = 0, mc2 = 0;
	for (int i = 1; i <= n; ++i) 
		if (c[i].size() && (!mc1 || w[i] < w[mc1])) mc1 = i;
	for (int i = 1; i <= n; ++i) 
		if (c[i].size() && i != mc1 && (!mc2 || w[i] < w[mc2])) mc2 = i;
	if (!mc2 || w[mc1] + w[mc2] > Y) return puts("1"), 0;
	int res1 = 0, res2 = 1;
	for (int i = 1, cnt; i <= n; ++i) {
		if (!c[i].size() || w[i] + w[mc1] > Y) continue;
		cnt = 0;
		for (vector<int>::iterator j = c[i].begin(); j != c[i].end(); ++j) {
			cnt += ((*j) + w[mc1 - i ? mc1 : mc2] <= Y || (*j) + w[i] <= X);
		}
		res1 += cnt, res2 = 1ll * caf[cnt] * res2 % mod;
	}
	printf("%d\n", 1ll * fac[res1] * res2 % mod);
	return 0; 
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}


Measured memory_bytes: 11648
#define DEBUG 0

/**
 * File    : E.cpp
 * Author  : Kazune Takahashi
 * Created : 2019-5-25 21:14:31
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(10101010));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

const int MAX_SIZE = 1000010;
const long long MOD = 1000000007;

long long inv[MAX_SIZE];
long long fact[MAX_SIZE];
long long factinv[MAX_SIZE];

void init()
{
  inv[1] = 1;
  for (int i = 2; i < MAX_SIZE; i++)
  {
    inv[i] = ((MOD - inv[MOD % i]) * (MOD / i)) % MOD;
  }
  fact[0] = factinv[0] = 1;
  for (int i = 1; i < MAX_SIZE; i++)
  {
    fact[i] = (i * fact[i - 1]) % MOD;
    factinv[i] = (inv[i] * factinv[i - 1]) % MOD;
  }
}

long long C(int n, int k)
{
  if (n >= 0 && k >= 0 && n - k >= 0)
  {
    return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
  }
  return 0;
}

long long power(long long x, long long n)
{
  if (n == 0)
  {
    return 1;
  }
  else if (n % 2 == 1)
  {
    return (x * power(x, n - 1)) % MOD;
  }
  else
  {
    long long half = power(x, n / 2);
    return (half * half) % MOD;
  }
}

long long gcd(long long x, long long y)
{
  return y ? gcd(y, x % y) : x;
}

ll N, M, K;
ll ans = 0;

void solve()
{
  for (ll i = 0; i < M - 1; i++)
  {
    ll t = (M - i) * (M - 1 - i) / 2;
    t %= MOD;
    t *= N;
    t %= MOD;
    t *= N;
    t %= MOD;
    t *= C(N * M - 2, K - 2);
    t %= MOD;
#if DEBUG == 1
    cerr << "i = " << i << ", t = " << t << endl;
#endif
    ans += t;
    ans %= MOD;
  }
}

int main()
{
  init();
  cin >> N >> M >> K;
  solve();
  swap(N, M);
  solve();
  cout << ans << endl;
}

Measured memory_bytes: 23680
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

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

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> N;
	vector< int > A(N);
	rep(i, N) cin >> A[i];
	sort(A.begin(), A.end());
	vector< int > B(1e6 + 10, 0);
	rep(i, N) B[A[i]]++;
	for (int i = 1; i <= 1e6; i++)
		if (B[i] > 0) {
			for (int j = i + i; j <= 1e6; j += i) {
				B[j] = 0;
			}
			if (B[i] > 1)
				B[i] = 0;
		}
	int ans = 0;
	for (auto b : B) {
		if (b)
			ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12764
def main():
    N = int(input())
    comment = []

    for i in range(1, N + 1):
        A = int(input())
        for j in range(1, A + 1):
            c = [i]
            c.extend(list(map(int, input().split())))
            comment.append(c)

    ans = 0
    for i in range(1, 2**N):
        flg = True
        for h, t, c in comment:
            #発言者が正直者か
            if i & (1 << h - 1):
                #発言が適切か
                if ((i >> t - 1) & 0b1) ^ c:
                    flg = False
                    break
        
        if flg:
            tmp = 0
            for j in range(N):
                if i & (1 << j):
                    tmp += 1
            
            ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9108
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let ab: Vec<u32> = read_vec();
    let a = ab[0];
    let b = ab[1];
    if a > 12 {
        println!("{}", b);
    } else if a > 5 {
        println!("{}", b / 2);
    } else {
        println!("0");
    }
}


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

int main() {
  int N; cin >> N;
  vector<pair<long long, long long>> R(N);
  for (int i = 0; i < N; i++) {
    long long X, L; cin >> X >> L;
    R.at(i) = make_pair(X+L, X-L);
  }
  sort(R.begin(), R.end());
  int ans = 0;
  long long pos = -1000000007;
  for (int i = 0; i < N; i++) {
    if (pos <= R.at(i).second) {
      ans++;
      pos = R.at(i).first;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
mod = 998244353
a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

dp[a][b] = 1
if d > b:
    dp[a][b+1] = a
if c > a:
    dp[a+1][b] = b
for i in range(b+2,d+1):
    dp[a][i] = dp[a][i-1]*a%mod

for i in range(a+2,c+1):
    dp[i][b] = dp[i-1][b]*b%mod

for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        dp[i][j] = (dp[i][j-1] * i % mod + dp[i-1][j] * j % mod - dp[i-1][j-1]*(i-1)*(j-1)%mod + mod) % mod

#print(dp)
print(dp[c][d] % mod)

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

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define itrdebug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

void solve(long long X, long long Y){
    // tsuru A, kame X - A
    // 2 * A + 4 * (X-A) = Y
    // 2A = 4X - Y
    cout << ((4*X - Y) >= 0 && (4*X - Y) % 2 == 0 && (X - (4*X - Y)/2) >= 0 ? "Yes" : "No") << endl;
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    solve(X, Y);
    return 0;
}


Measured memory_bytes: 3680
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int main()
{
	int N, W;
	cin >> N >> W;
	vector<ll> w(N);
	vector<ll> v(N);
	for (auto i = 0; i < N; ++i)
	{
		cin >> w[i] >> v[i];
	}

	set<ll> s;
	for (auto i = 1; i <= N; ++i)
	{
		for (auto j = 0; j <= i * 3; ++j)
		{
			auto temp = w[0] * i + j;
			if (temp <= W)
			{
				s.insert(temp);
			}
		}
	}
	s.insert(W);

	vector<ll> x;
	x.push_back(0);
	for (auto v : s)
	{
		x.push_back(v);
	}

	vector<vector<ll>> dp(N + 1, vector<ll>((int)x.size(), -1));
	dp[0][0] = 0;
	for (auto i = 0; i < N; ++i)
	{
		for (auto j = 0; j < (int)x.size(); ++j)
		{
			dp[i + 1][j] = dp[i][j];
			if (j <= 0)
			{
				continue;
			}

			auto weight = x[j];
			if (weight < w[i])
			{
				continue;
			}
			auto it = lower_bound(x.begin(), x.end(), weight - w[i]);
			if (it == x.end() || *it != weight - w[i])
			{
				continue;
			}
			auto k = it - x.begin();
			if (dp[i][k] < 0)
			{
				continue;
			}
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + v[i]);
		}
	}

	auto ans = 0ll;
	for (auto i = 0; i < (int)x.size(); ++i)
	{
		ans = max(ans, dp[N][i]);
	}
	cout << ans << endl;

	return 0;
}

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

int main() {
  int N ;
  cin >> N ;
  int l ,r ;
  int p = 0;
  for (int i = 0; i < N; i++ ){
    cin >> l >> r;
    p += r - l + 1 ;
  }
  cout << p << endl;
}


Measured memory_bytes: 3608
a, b, c, x = 4.times.map { gets.to_i }
cnt = 0

(0..a).each do |i|
  (0..b).each do |j|
    (0..c).each do |k|
      cnt += 1 if i * 500 + j * 100 + k * 50 == x
    end
  end
end

p cnt

Measured memory_bytes: 14308
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace arc_061_A
{
    class Program
    {
        public static long a(int n, string str, bool[] plus)
        {
            if (n == str.Length - 1)
            {
                string u = "";
                for (int i = 0; i < str.Length - 1; i++)
                {
                    u += str[i];
                    if (plus[i]) { u += '+'; }
                }
                u += str[str.Length - 1];
                return u.Split('+').Select(long.Parse).ToArray().Sum();
            }
            bool[] aft = new bool[str.Length-1];
            for(int i = 0; i < aft.Length; i++)
            {
                if (i == n) { aft[n] = true; }
                else { aft[i] = plus[i]; }
            }
            return a(n + 1, str, plus) + a(n + 1, str, aft);
        }
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            var plus = new bool[str.Length - 1];
            for(int i = 0; i < plus.Length; i++)
            {
                plus[i] = false;
            }
            Console.WriteLine(a(0,str,plus));
            Console.ReadLine();
        }
    }
}


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

namespace ALDS1_3
{
    class Progarm
    {
        static void Main()
        {
            var i = new LinkedList<string>();
            var l = int.Parse(Console.ReadLine());
 
            for (var j = 0; j < l; j++)
            {
                var _t = Console.ReadLine().Split();
                 
                if (_t.Length == 1)
                {
                    if (_t[0] == "deleteFirst")
                        i.Remove(i.First);
                    else
                        i.Remove(i.Last);
                }
                else
                {
                    if (_t[0] == "insert")
                        i.AddFirst(_t[1]);
                    else
                    {
                        var node = i.Find(_t[1]);
                        if (node != null) i.Remove(node);
                    }
                        
                }        
            }

            Console.WriteLine(string.Join(" ", i.ToArray()));
         }
    }
}

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


int main(){
  string s;
  cin >> s;
  int l = s.length();
  int one = 0;
  int zero = 0;
  for(int i=0;i<l;i++){
    if(s[i]=='0')zero++;
    if(s[i]=='1')one++;
  }
  cout << l - abs(one - zero);
  return 0;
}

Measured memory_bytes: 512
//          ★★ ASHWINI SHARMA ★★ 
#include <bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
#define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define ull unsigned long long int
#define ll long long int
#define ui unsigned int
#define pb push_back
 
#define PI 3.1415926535897932385
#define INF 1e9
#define EPS 1e-7
#define MAXN 1000000005
#define MOD 1000000007 
                              //          ★★ ASHWINI SHARMA ★★      
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll exp(ll x, ll y, ll p)
{
    ll res = 1;   
    x = x % p;  
    while (y > 0)
    {
        if (y & 1)    
            res = (res*x) % p;
        y = y>>1;     
        x = (x*x) % p; 
    }
    return res;
}



int main() {
   
    fastio;
    string s;
    cin >> s;
    int n = s.length();
    int sum = 0;
    rep(i, n)
    {
        int f = s[i] - '0';
        sum = sum % 9 + f % 9;
        sum %= 9;
    }
    if(!sum)
        cout << "Yes";
    else
        cout << "No";
    return 0; 
}

Measured memory_bytes: 3732
import re
class c:
	def __str__(self):
		return str(self.x)
	def __init__(self,value):
		self.x=value
	def __add__(self,value):
		return c(self.x+value.x)
	def __sub__(self,value):
		return c(self.x-value.x)
	def __mul__(self,value):
		return c(self.x*value.x)
	def __truediv__(self,value):
		return c(int(self.x/value.x))
n=int(input())
for i in range(n):
	s=input()[:-1]
	s=re.sub(r'(\d+)',r'c(\1)',s)
	print(eval(s))

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

int main(){
    string s; cin >> s;
    reverse(s.begin(),s.end());
    map<int,int> mp;
    int n = s.size();
    int rec=1;
    int t = 0;
    long long ans = 0;
    rep(i,n){
        mp[t]++;
        t+=(s[i]-'0') * rec;
        t%=mod;
        rec = rec*10%mod;
        ans += mp[t];
    }
    /*for(auto itr=mp.begin();itr!=mp.end();++itr){
        ans += itr->second*(itr->second-1)/2;
    }*/
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
vector<string> ans , v;
map<string , int> mp;
int main(){
    int n ;
    cin >> n;
    int mx = 0;
    for(int i = 0 ; i < n ; i++){
        string s;
        cin >> s;
        mp[s]++;
        mx = max(mx , mp[s]);
        if(mp[s] == 1)
            v.push_back(s);
    }
    for(int i = 0 ; i < v.size() ; i++){
        if(mp[v[i]] == mx)
            ans.push_back(v[i]);
    }
    sort(ans.begin() , ans.end());
    for(int i = 0 ; i < ans.size() ; i++)
        cout << ans[i] << endl;
    return 0;
}

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

typedef struct List {
	struct List *next;
	int v;
} list;

typedef struct {
	int *par, *size, *height;
} UF_forest;

void UF_initialize(UF_forest *F, int n)
{
	int i;
	F->par = (int*)malloc(sizeof(int) * (n + 1));
	F->size = (int*)malloc(sizeof(int) * (n + 1));
	F->height = (int*)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) {
		F->par[i] = i;
		F->size[i] = 1;
		F->height[i] = 1;
	}
}

void UF_merge(UF_forest *F, int u, int v)
{
	for (; F->par[u] != u; u = F->par[u]);
	for (; F->par[v] != v; v = F->par[v]);
	if (u == v) return;
	else if (F->height[u] > F->height[v]) {
		F->par[v] = u;
		F->size[u] += F->size[v];
	} else {
		F->par[u] = v;
		F->size[v] += F->size[u];
		if (F->height[u] == F->height[v]) F->height[v]++;
	}
}

int UF_root(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return v;
}

int UF_size(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return F->size[v];
}

int main()
{
	int i, N, x[100001], y[100001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d %d", &(x[i]), &(y[i]));

	list *p, *q, *X[100001] = {}, *Y[100001] = {}, d[200003];
	for (i = 1; i <= N; i++) {
		d[i*2].v = y[i];
		d[i*2+1].v = x[i];
		d[i*2].next = X[x[i]];
		d[i*2+1].next = Y[y[i]];
		X[x[i]] = &(d[i*2]);
		Y[y[i]] = &(d[i*2+1]);
	}

	UF_forest F[2];
	UF_initialize(&(F[0]), 100000);
	UF_initialize(&(F[1]), 100000);
	for (i = 1; i <= 100000; i++) {
		if (X[i] == NULL) continue;
		for (p = X[i]; p != NULL; p = p->next) {
			UF_merge(&(F[1]), X[i]->v, p->v);
			for (q = Y[p->v]; q != NULL; q = q->next) UF_merge(&(F[0]), i, q->v);
		}
	}
	for (i = 1; i <= 100000; i++) {
		if (Y[i] == NULL) continue;
		for (q = Y[i]; q != NULL; q = q->next) {
			UF_merge(&(F[0]), Y[i]->v, q->v);
			for (p = X[q->v]; p != NULL; p = p->next) UF_merge(&(F[1]), i, p->v);
		}
	}
	
	int r, flag[100001] = {};
	long long ans = 0;
	for (i = 1; i <= N; i++) {
		r = UF_root(&(F[0]), x[i]);
		if (flag[r] == 1) continue;
		else flag[r] = 1;
		ans += (long long)UF_size(&(F[0]), r) * UF_size(&(F[1]), y[i]);
	}
	printf("%lld\n", ans - N);
	fflush(stdout);
	return 0;
}

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







int main()
{



int a,b,c,d;
cin >> a >> b >> c >> d;

if(abs(a - c) <= d) 
{
	cout << "Yes";
	return 0;
}


	if(abs(a - b) <= d && abs(b - c) <= d) 
	{
		cout << "Yes";
		return 0;
	}


cout << "No";

	return 0;
}		


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

long long keta (long long num) {
  while(num/10>0) {
    num/=10;
  }
  return num;
}

int main() {
  long long n;
  cin >> n;
  vector<vector<long long>> a(10, vector<long long>(10,0));
  for(long long i=0;i<=n;i++) {
    a.at(keta(i)).at(i%10)++;
  }
  long long ans=0;
  for(long long i=1;i<10;i++) {
    for(long long j=1;j<10;j++) {
      ans+=a.at(i).at(j)*a.at(j).at(i);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=100010;

int n,a[maxn],b[maxn],c;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++){
    	if(a[i]-1>=0)b[a[i]-1]++;else c++;
    	b[a[i]]++;b[a[i]+1]++;
    }
    int ans=c;
    for(int i=0;i<=maxn;i++)ans=max(ans,b[i]);
    printf("%d",ans);
    return 0;
}

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

int main(){
  int a,b,c,d,e,n,ans=0;
  while(cin >> n ){
  for(int i=0;i<=9;i++){
    for(int j=0;j<=9;j++){
      for(int k=0;k<=9;k++){
        for(int l=0;l<=9;l++){
          if(i+j+k+l==n){
            ans++;
        }
        }
      }
    }
  }
        cout << ans << endl;
        ans =0;
}
}

Measured memory_bytes: 1156
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<list>
#include<stack>
//#include<unordered_map>
using namespace std;
#define ll long long 
const int mod=1e9+7;
const int inf=1e9+7;

//const int maxn=
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    
    int a,b;
    
    cin>>a>>b;
    
    cout<<max(0,a-2*b)<<endl;
     
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int a[100];
long long ans[405][405];
long long int counter(int l, int r){
    if(l==r){
        return 0;
    }
    if(ans[l][r] != -1)
        return ans[l][r];
    long long int minres = -1;
    long long int sum = 0;
    for(int i=l; i<r; i++){
        sum = sum + a[i];
        if(minres == -1)
            minres = counter(l,i)+counter(i+1,r);
        else
            minres = min(minres,counter(l,i)+counter(i+1,r));
    }
    // cout << l << " " << r << " " << minres+sum+a[r] << "\n";
    return ans[l][r] = minres+sum+a[r];
}
int main(){
    int n;
    cin >> n;
    memset(ans, -1, sizeof(ans));
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    cout << counter(0,n-1);
    return 0;
}

Measured memory_bytes: 4772
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		char ATCG = sc.next().charAt(0);
		if('A' == ATCG) {
			System.out.println("T");
		}else if(ATCG == 'T') {
			System.out.println("A");
		}else if(ATCG == 'G') {
			System.out.println("C");
		}else if(ATCG == 'C') {
			System.out.println("G");
		}
	}

}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
#define w(t) int t;cin>>t;while(t--)
#define pb   push_back
#define mk   make_pair
#define prDouble(x) cout<<fixed<<setprecision(10)<<x
typedef long long ll;
const ll mod=1e9+7;
double dp[3001][3001];
double solve(vector<double>&a,int i,int x){
	if(x==0)return 1;
	if(i==0)return 0;
    if(dp[i][x]>-0.9)return dp[i][x];
	return dp[i][x]=a[i]*solve(a,i-1,x-1)+(1-a[i])*solve(a,i-1,x);
}

int main()
{

	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr);
    int n;cin>>n;
    vector<double>A(n+1);
    for(int i=1;i<=n;i++)cin>>A[i];
    memset(dp,-1,sizeof dp);
    prDouble(solve(A,n,(n+1)/2));
    return 0; 
}
/*
here the problem says that i need more heads than tails
1.so if I flip n coins then i need atleast (n+1)/2 heads i add to avoid taking celi value
2.so I will define my dp as dp[n][(n+1)/2]
3.dp[i][x] on tossing first ith coins the probability of getting >=x heads
4.so if i get dp[i][x] head then i need x-1 heads in previous tossing
5. so if i get dp[i][x] tails then i need 
*/



Measured memory_bytes: 70784
#include <iostream>
#include <stdexcept>
#include <cassert>
#include <cmath>
#include <vector>
#include <string>
#include <set>
using namespace std;


void dfs(vector<vector<int>>& g, vector<bool>& checked, int i, set<int>& people) {
  people.insert(i);
  checked[i] = true;
  for (int j : g[i]) {
    if (!checked[j]) dfs(g, checked, j, people);
  }
}


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

  int a, b;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    cin >> a >> b;
    g[a - 1].push_back(b - 1);
    g[b - 1].push_back(a - 1);
  }

  int maxGroupSize = 0;
  set<int> people;
  vector<bool> checked(N, false);
  for (int i = 0; i < N; i++) {
    people.clear();
    dfs(g, checked, i, people);
    maxGroupSize = max(maxGroupSize, (int) people.size());
  }
  cout << maxGroupSize << endl;

  return 0;
}


Measured memory_bytes: 38936
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <string>
#include <sstream>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define pll pair<long long,long long>
#define pld pair<long double,long double>
#define ios     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll mod=1000000007;
ll gcd (ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ll fastexp(ll x ,ll n)
{
    ll result =1;
    while(n>0)
    {
        if(n%2==1)
            result*=x;
        x*=x;
        n=n/2;
    }
    return result;
}

ll modularExp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n%2==1)
            result=(result*x)%mod;
        x=((x%mod)*(x%mod))%mod;
        n=n/2;
    }
    return (result)%mod;
}
bool isPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
    return true;
}
bool mycomp(pll &a,pll &b)
{
    if(a.F!=b.F)
        return a.F < b.F;
    else
        return a.S < b.S;
}

ll INF=1e18;

void solve()
{
     ll n,k;
     cin>>n>>k;
     vector<ll> v(n+1),w(n+1);
     ll i,j;
     ll vsum=0;
     for(i=1;i<=n;i++)
     {
          cin>>w[i]>>v[i];
          vsum+=v[i];
     }
     vector<ll> dp(vsum+1,INF);
     dp[0]=0;
     for(i=1;i<=n;i++)
     {
          for(j=vsum;j>=v[i];j--)
               dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
     }
     for(i=vsum;i>=0;i--)
     {
          if(dp[i]<=k)
          {
               cout<<i<<" ";
               return ;
          }
     }
     
     
     
     
}

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

Measured memory_bytes: 1024
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long

#define INF 999999999

using namespace std;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
// input
int x,y,z;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> x >> y >> z;

    cout << floor((x-z)/(y+z)) << "\n";
}

Measured memory_bytes: 256
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System;

namespace AtCoder
{
    class Program
    {
        private static long mod = 1000000007;
        static void Main(string[] args)
        {
            var n = long.Parse(ReadLine());
            //var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();

            var sqrt = (int)Sqrt(n);

            var dictionary = new Dictionary<int, int>();
            for(var i = 1; i <= sqrt; i++)
            {
                for(var j = 1; j <= sqrt; j++)
                {
                    for(var k = 1; k < sqrt; k++)
                    {
                        var value = i * i + j * j + k * k + i * j + j * k + i * k;
                        if (!dictionary.ContainsKey(value))
                        {
                            dictionary.Add(value, 0);
                        }
                        dictionary[value]++;
                    }
                }
            }

            for(var i = 1; i <= n; i++)
            {
                if(dictionary.ContainsKey(i))
                {
                    WriteLine(dictionary[i]);
                }
                else
                {
                    WriteLine(0);
                }
            }
        }
    }
}


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

int main(void){
  	
string s;
cin>>s;
  
int n=1;

if(s[0]=='R' && s[1]=='R' && s[2]=='R'){
	n=3;
}else if(s[0]=='R' && s[1]=='R'){
	n=2;
}else if(s[1]=='R' && s[2]=='R'){
	n=2;
}else if(s[0]=='S' && s[1]=='S' && s[2]=='S'){
	n=0;
}
  
cout<<n;
	
  
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
const int ININF = 1000000;
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++)
            par[i] = i;
    }

    int
    root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if(par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x);      // xの根をrx
        int ry = root(y);      // yの根をry
        if(rx == ry)
            return; // xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] =
            ry; // xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
vector<int> p;
vector<int> q;
vector<vector<int>> G;
int main() {
    int N, M;
    cin >> N >> M;
    p.assign(N, 0);
    q.assign(N, 0);
    rep(i, 0, N) {
        cin >> p[i];
        p[i]--;
        q[p[i]]=i;
    }
    UnionFind tree(N);
    rep(i, 0, M) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        tree.unite(x, y);
    }
    int res = 0;
    rep(i, 0, N) {
        //cout << "root" << tree.root(i) << "," << tree.root(q[i])<<endl;
        if(tree.same(i, q[i])) {
            res++;
        } 
    }
    cout << res << endl;
}


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

int main(void){
   
  string s;
  cin >> s;
  int len = s.size();
  for(int i=0;i<len;i++){
      if(s[i] == ',') s[i] = ' ';
      cout << s[i];
  }
  cout <<endl;
}

Measured memory_bytes: 3572
def factorization(n):
    arr = []
    temp = n
    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


N = int(input())
div = factorization(N)

# print(div)
if N == 1:
    print(0)
    exit()

ans = 0
# print(div)
for d in div:
    c = d[1]
    i = 1

    while c >= 0:
        c -= i
        if c >= 0:
            ans += 1
        i += 1

print(ans)


Measured memory_bytes: 9424
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500500;
int n,m,k;
ll r,D,X;
int main()
{
	cin>>r>>D>>X;
	for(int i=1;i<=10;i++)
	{
		X=r*X-D;
		cout<<X<<endl;
	}
}


Measured memory_bytes: 256
from operator import itemgetter
N = int(input())
XYZ = [list(map(int, input().split())) for _ in range(N)]

XYZ.sort(key=itemgetter(2), reverse=True)

for x in range(101):
    for y in range(0, 101):
        H = XYZ[0][2]+abs(XYZ[0][0]-x)+abs(XYZ[0][1]-y)
        judge = True
        for xyz in XYZ[1:]:
            if xyz[2] == max(H-abs(xyz[0]-x)-abs(xyz[1]-y),0):
                pass
            else:
                judge = False
                break
        if judge:
            X = x
            Y = y
            break
    if judge:
        break
print(X, Y, H)

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


int main(){

  int n;
  cin >> n;
  cout << (n/2)*(n-n/2) << endl;



  return 0;
}


Measured memory_bytes: 256
N, K = map(int,input().split())
U = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
for d in list(map(int,input().split())):
    if d in U:
        U.remove(d)

def check(n):
    for s in str(n):
        if int(s) not in U:
            return False
    if n >= N:
        return True
    else:
        return False

ans = N
while not check(ans):
    ans += 1

print(ans)



Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int k;
    string s = "Yay!";
    vector<int>v(5);

    for(int i = 0;i < 5;i++)
        cin >> v[i];
    
    cin >> k;

    for(int i = 0;i < 4;i++){
        for(int j = i+1;j < 5;j++){
            if(abs(v[i]-v[j]) > k)
                s = ":(";
        }
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    d = []
    for _ in range(h):
        tmp = list(input())
        d.extend(tmp)

    c = collections.Counter(d)

    flg1 = w % 2
    flg2 = h % 2
    even_pocket = h * flg1 + w * flg2 - flg1 * flg2 * 2
    odd_pocket = flg1 * flg2

    ans = True
    for k, v in c.items():
        even_pocket -= ((v % 4) // 2) * 2
        odd_pocket -= v % 2
        if even_pocket < 0 or odd_pocket < 0:
            ans = False
            break

    print("Yes" if ans else "No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 5096