akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//#include <boost/algorithm/string.hpp>
using namespace std;


void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}


#define Vec(a) vector<a>

#define ll long long
#define ld long double
#define ull unsigned long long
#define ull unsigned long long
#define mod 1000000007
#define pi (3.1415926)

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

#define scd(a)  scanf("%lld",&a)
#define scdd(a,b)	scanf("%lld%lld",&a,&b)
#define scddd(a,b,c)	scanf("%lld%lld%lld",&a,&b,&c)
#define ptab(a)	printf("%lld ",a)
#define pdn(a)	printf("%lld\n",a)
#define pddn(a,b)	printf("%lld %lld\n",a,b)
#define pdddn(a,b,c)	printf("%lld %lld %lld\n",a,b,c)

#define Filein(N) freopen("N", "r", stdin);
#define Fileout(N) freopen("N", "w", stdout);

#define forr(n) for(ll i=0;i<n;i++)
#define rev(n) for(ll i=n-1;i>=0;i--)
#define forp(x, y) for(ll i=x;i<y;i++)
#define loop( j, k, in) for (ll i=j ; i<k ; i+=in)

#define in  cin>>
#define out cout<<
#define en "\n"
#define sp " "
#define eps 1.0E-14
#define l length()
#define preci(x) cout << fixed<<setprecision(x)
#define inf LONG_LONG_MAX
#define ninf LONG_LONG_MIN


void odd(int n)
    {
    bool b=1;
        int x = sqrt(n);
    for (int i=2 ; i<=x ; ++i)

    {
        if(n%i == 0) {cout << "NO" << sp; b = 0;  break;}
    }
    if (b)
    cout << "Yes" << sp;
    b=1;
    }
ll fact(int n ){

long long fact =1;

for (int i =2 ;i<=n;++i)

{
    fact*=i;
}
return fact;
}


ll sum (int n ){return ((n*(n+1)) / 2) ;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int a[4];

int main()
{
    init();
    string s; cin>>s;

    s == "ABC"? cout << "ARC": cout << "ABC";
}



Measured memory_bytes: 3608
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 500000;
int used[N], cycle[N], deg[N], p[N], b[N], mark[N], n;
vector < int > g[N], G[N], in[N], c[N];
map < pair < int, int >, int > ff;
void dfs1(int v){
    used[v] = 1;
    for (auto u: g[v]){
        if (used[u]){
            if (u == p[v] || cycle[u]) continue;
            cycle[v] = 1;
            while(v != u){
                v = p[v];
                cycle[v] = 1;
            }
        } else{
            p[u] = v;
            dfs1(u);
        }
    }
}
void dfs2(int v){
    for (auto u: G[v]){
        if (cycle[u]) continue;
        dfs2(u);
        c[v].pb(mark[u]);
    }
    sort(c[v].begin(), c[v].end());
    if (cycle[v]) return;
    mark[v] = -1;
    int pr = -1;
    for (auto i: c[v]){
        if (pr + 1 != i && i > pr){
            mark[v] = pr + 1;
            return;
        }
        pr = i;
    }
    if (mark[v] == -1) mark[v] = pr + 1;
}
void tr(int v, int x){
    memset(b, 0, sizeof(b));
    mark[v] = x;
    int pr = x;
    int v0 = v;
    for (auto u: in[v]) if (cycle[u]){
        v = u;
        break;
    }
    while(v != v0){
        for (auto i: c[v]) b[i] = v;
        b[pr] = v;
        for (int i = 0; i <= n + 2; i++){
            if (b[i] != v){
                mark[v] = i;
                break;
            }
        }
        pr = mark[v];
        for (auto u: in[v]) if (cycle[u]){
            v = u;
            break;
        }
    }
    for (int i = 1; i <= n; i++){
        set < int > a;
        int t = 0;
        while(!a.empty()) a.erase(a.begin());
        for (auto j: G[i]) a.insert(mark[j]);
        for (auto j: a){
            if (j != t) break;
            t++;
        }
        if (mark[i] != t) return;
    }
    cout << "POSSIBLE";
    exit(0);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++){
        int u, v;
        cin >> u;
        v = i;
        g[v].pb(u);
        g[u].pb(v);
        G[u].pb(v);
        if (ff[{v, u}]){
            cycle[v] = 1;
            cycle[u] = 1;
        }
        ff[{u, v}] = 1;
        in[v].pb(u);
        deg[u]++;
    }
    dfs1(1);
    for (int i = 1; i <= n; i++) if (cycle[i]) dfs2(i);
    for (int i = 1; i <= n; i++){
        if (cycle[i]){
            vector < int > cand;
            for (auto j: c[i]) b[j] = 1;
            for (int j = 0; j <= n + 5; j++) if (b[j] == 0) cand.pb(j);
            tr(i, cand[0]);
            tr(i, cand[1]);
            cout << "IMPOSSIBLE";
            return 0;
        }
    }
}


Measured memory_bytes: 120052
#include<stdio.h>
int main()
{
    int n,x,i,min=1000,sum=0,m;
    int a[105];
    scanf("%d %d",&n,&x);
    m=n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum=sum+a[i];
        if(min>a[i])
            min=a[i];
    }
    if((x-sum)<min)
    {
        printf("%d\n",n);
    }
    else
    {
        m=m+(x-sum)/min;
        printf("%d\n",m);
    }
    return 0;

}


Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main()
{
  int i,eight,ten,tax8,tax10,judge;
  cin>>eight>>ten;
  
  for(i=0;i<1250;i++)
  {
    tax8=i*8/100;
    tax10=i/10;
    if(eight==tax8&&ten==tax10)
    {
      cout<<i;
      judge=1;
      goto end;
    }
  }
  cout<<"-1";
  end:
  ;
}

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

using namespace std;
int dp[1024][100001];

void dfs(int v, int L, int &ans, vector<int> &W, vector<int> &V, int now=0) {
    if(v < 1024) {
        ans = max(ans, dp[v][L] + now);
    } else {
        dfs(v/2, L, ans, W, V, now);
        if(L - W[v] >= 0) {
            dfs(v/2, L - W[v], ans, W, V, now+V[v]);
        }
    }
}

int main(void) {
    int N;
    cin >> N;
    vector<int> V(N+1), W(N+1);
    for(int i=1; i<=N; i++) {
        cin >> V[i] >> W[i];
    }

    for(int i=1; i<1024; i++) {
        for(int k=100001; k>=0; k--) {
            if(k - W[i] < 0) {
                dp[i][k] = dp[i/2][k];
            } else {
                dp[i][k] = max(dp[i/2][k - W[i]] + V[i], dp[i/2][k]);
            }
        }
    }

    int Q;
    cin >> Q;
    while(Q--) {
        int v, L;
        cin >> v >> L;
        int ans = 0;
        dfs(v, L, ans, W, V);
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 404916
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include <string>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }


int main(){
	ll a,b,c; cin >>a>>b>>c;
	if(a%2==0||b*c%2==0){
		cout << 0 << endl;
		return 0;
	}
	cout << min({a*b,b*c,c*a}) << endl;
}

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

int main(){
        int i,j,X;
        cin >> X;
        for(i=-120;i<=120;++i){
                for(j=-120;j<=120;++j){
                        if(i<0&&j>0) continue;
                        if(pow(i,5)-pow(j,5)==X){
                                cout << i << " " << j << endl;
                                return 0;
                        }
                }
        }
}

Measured memory_bytes: 3960
from sys import stdin
input = stdin.readline

N = int(input())
s = [int(input())for _ in range(N)]

s.sort()

ans = sum(s)

if ans % 10 != 0:
    print(ans)
    exit()

for i in s:
    if i % 10 != 0:
        print(ans - i)
        exit()

print(0)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

int r, p, s;

int opnum(char x) {
    if (x == 's') {
        return (r);
    }
    if (x == 'r') {
        return (p);
    }
    if (x == 'p') {
        return (s);
    }
    return 0;
}
char op(char x) {
    if (x == 's') {
        return ('r');
    }
    if (x == 'r') {
        return ('p');
    }
    if (x == 'p') {
        return ('s');
    }
    return 0;
}

int main() {
    long a, b, n, k, ans = 0;
    cin >> n;
    if (n % 2 == 0) {
        cout << 0.5 << endl;
    } else {
        a = n / 2 + 1;
        cout << double(a) / double(n) << endl;
    }
}

Measured memory_bytes: 256
N=int(input())
S = input()

W=[1 if S[0]=="." else 0]
ans=float("inf")

for i in range(1,N):
  if S[i]==".":
    W.append(W[-1]+1)
  else:
    W.append(W[-1])
    
if W[-1]==0 or W[-1]==N:
  print(0)
  exit()

for i in range(N):
  cost_W = i+1-W[i]
  cost_B = W[-1]-W[i]
  cost=cost_W+cost_B
  #print(N, W[-1], i+1, W[i])
  #print(i,"cost_W:",cost_W,"cost_B:",cost_B,"Total",cost)
  ans=min(ans,cost)
ans=min(W[-1],N-W[-1],ans)
print(ans)

Measured memory_bytes: 11136
from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    white=0
    black=0
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            black+=1
        if s[y][x]=='.':
            white+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))
    ans+=(black*white)

field=[[False]*w for j in range(h)]                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.' and field[i][j]==False:
            field[i][j]=True
            bfs(i,j)

print(ans)

Measured memory_bytes: 6124
#include <iostream>
#include <cmath>
#include <numeric>
#define MAX 1000000
using namespace std;

bool isPrime(int x) {
  if(x == 2) {
	return true;
  }
  
  if(x < 2 || x % 2 == 0) {
	return false;
  }
  for(int i = 3; i <= sqrt(x); i += 2) {
	if(x % i == 0) {
	  return false;
	}
  }
  return true;
}

int main() {
  int n;
  bool a[MAX] = {};

  for(int i = 1; i < MAX; ++i) {
	if(isPrime(i)) {
	  a[i] = true;
	}
  }
  /*
  for(int i = 1; i < MAX; ++i) {
	if(isPrime(i)) {
	  cout << i << " ";
	}
  }
  */
  while(cin >> n) {
	cout << accumulate(&a[1], &a[n + 1], 0) << endl;
  }
  return 0;
}

/*-- primitive algorithm --*/
/*
bool isPrime(int n) {
  for(int i = 2; i < n; ++i) {
	if(n % i == 0) return false;
  }
  return true;
}
*/

Measured memory_bytes: 3984
a=-1,A=65,d;
char
*N="GKSOCNWLDFVTBRXHAJUPEMQI",
*E="PHLTIDOXQAGWECSUMBKVJFNR",
*R="BCDAFGHEJKLINOPMRSTQVWXU",
s[9];
main(c)
{
for(;c-48&&scanf("%s",s);)
{
if((c=*s)<A)
~a&&printf("%d\n",a),
a=d=0;
if(c=='N')d=N[d]-A;
if(c=='E')d=E[d]-A;
if(c=='W')d=E[E[E[d]-A]-A]-A;
if(c=='S')d=N[N[N[d]-A]-A]-A;
if(c=='R')d=R[d]-A;
if(c=='L')d=R[R[R[d]-A]-A]-A;
a+=d/4+1;
}
}

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

class Main{
		
		public static void parallel(ArrayList<Double> a){
			double x1,y1,x2,y2,x3,y3,x4,y4;
			x1 = a.get(0);
			y1 = a.get(1);
			x2 = a.get(2);
			y2 = a.get(3);
			x3 = a.get(4);
			y3 = a.get(5);
			x4 = a.get(6);
			y4 = a.get(7);
			if((y2-y1)/(x2-x1) == (y4-y3)/(x4-x3))
				System.out.println("YES");
			else System.out.println("NO");
		}
		
		public static void main(String args[]) throws IOException{
			String str;
			ArrayList <Double> inp = new ArrayList<Double>();

			Scanner scan = new Scanner(System.in);
			
			str = scan.next();
			
			while(scan.hasNext()){
				inp.clear();
				for(int i=0;i<8;i++){
					str = scan.next();
					inp.add(Double.parseDouble(str));
				}
				parallel(inp);
			}
		}
}

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

int main(){
    int k;
    cin >> k;
    int odd = 0;
    int even = 0;
    if(k % 2 != 0){
        odd = k / 2 + 1;
        even = k / 2;
    } else {
        odd = k / 2;
        even = k / 2;
    }
    int ans = odd * even;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int i,a,b,k;
	scanf("%d %d %d",&a,&b,&k);
	for(i=0;i<k;i++)
	{
		if(i%2==0)
		{
			b+=(a/2);
			a/=2;
		}
		else
		{
			a+=(b/2);
			b/=2;
		}
	}
	printf("%d %d",a,b);
}


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

using namespace std;

const int mod = 1e9 + 7;

long long tab_1[2005], tab_2[2005], dp[2005][2005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    for (long long i = 1; i <= n; i++)
        cin >> tab_1[i];
    for (long long i = 1; i <= m; i++)
        cin >> tab_2[i];
    for (long long i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            dp[i][j] = (long long)dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            if (tab_1[i] == tab_2[j])
                dp[i][j] = (long long)dp[i][j] + dp[i - 1][j - 1] + 1;
            dp[i][j] %= mod;
            if (dp[i][j] < 0)
                dp[i][j] += mod;
        }
    cout << (dp[n][m] + 1) % mod << "\n";
    return 0;
}

Measured memory_bytes: 34916
import sys
from heapq import heappop, heappush
input = sys.stdin.readline


class Data :
    def __init__():
        pass
    def __init__(self, pos, step, cost):
        self.pos = pos
        self.step = step
        self.cost = cost
    def __lt__(self, right):
        return self.cost < right.cost

def dijkstra(N, S, T, edges):
    inf = 10 ** 9 + 7
    dis = []
    for i in range(N + 1):
        dis.append([inf, inf, inf])

    que = []
    dis[S][0] = 0
    heappush(que, Data(S, 0, 0))
    while (len(que)):
        now_d = heappop(que)
        if dis[now_d.pos][now_d.step] < now_d.cost:
            continue

        for edge in edges[now_d.pos] :
            next_d = Data(edge[0], (now_d.step + 1) % 3, now_d.cost + edge[1])
            if dis[next_d.pos][next_d.step] > next_d.cost:
                dis[next_d.pos][next_d.step] = next_d.cost
                heappush(que, next_d)
    
    if (dis[T][0] == 10 ** 9 + 7):
        return -1
    else :
        return dis[T][0] // 3

N, M = map(int, input().split())
edges = []
for i in range(N+1):
    edges.append([])
for i in range(M):
    u, v = map(int, input().split())
    edges[u].append((v, 1))
S, T = map(int, input().split())
print(dijkstra(N, S, T, edges))

Measured memory_bytes: 44152
fun main(args: Array<String>) {
    val ab = (1..3).map { readLine()!!.split(" ").map { it.toInt() } }.flatten()
    var flag = true
    for (i in 1..4) {
        if (!(ab.count { it == i } in 1..2)) {
            flag = false
            break
        }
    }
    println(if (flag) "YES" else "NO")
}

Measured memory_bytes: 37780
#include <bits/stdc++.h>
#define ll long long
#define p pair<int, int>
using namespace std;

int main() {
    int r, g, b, n;
    cin >> r >> g >> b >> n;
    int ans = 0;
    for (int i = 0; i <= 3000; i++) {
        for (int j = 0; j <= 3000; j++) {
            int t = n - i * r - j * g;
            if (t >= 0 && t % b == 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100

int main(){
  int n,a[MAX],ans = 0,i,j,tmp;

  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,a+i);
  }

  for(i = 0 ; i < n ; i++){
    for(j = n-1 ; j > i ; j--){
      if(a[j] < a[j-1]){
	tmp = a[j];
	a[j] = a[j-1];
	a[j-1] = tmp;
	ans++;
      }
    }
  }

  for(i = 0 ; i < n ; i++){
    if(i != n-1){
      printf("%d " ,a[i]);
    }else{
      printf("%d\n%d\n" ,a[i],ans);
    }
  }

  return 0;
}




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


int main(){
  long long  a,b,c,k;
  cin >> a>>b>>c>>k;
  if(k<=a){
    cout <<k<<endl;
    return 0;
  }
  if(a<k&&k<=a+b){
    cout << a << endl;
    return 0;
  }
  if(a+b<k&&a+b+c){
    cout << a-(k-a-b) << endl;
    return 0;
  }
  return 0;
}


Measured memory_bytes: 3624
S = set()

q = int(input())


for _ in range(q):
    
    command, *list_num = input().split()
    x = int(list_num[0])

    if   command == "0":
        # insert(x)
        S.add(x)
        print(len(S))
    elif command == "1":
        # find(x)
        if x in S:
            print(1)
        else:
            print(0)
    else:
        raise



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

n, m, l = map(int, input().split())
mw =[[float('inf')] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    mw[a-1][b-1] = c
    mw[b-1][a-1] = c

def warshall_floyd(d): # d: 隣接行列
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

d = warshall_floyd(mw)
mw =[[float('inf')] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            mw[i][j] = 1
dd = warshall_floyd(mw)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = dd[s-1][t-1]-1
    if ans > 10 ** 10:
        print(-1)
    else:
        print(ans)

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int N = 1005;
int n, m, k, ans;
int p[N];

int main() {
    cin >> n;
    p[1] = true;
    for (int i = 2; i < n; ++i) {
        for (int j = i * i; j <= n; j *= i) {
            p[j] = true;
        }
    }
    for (int i = n; i >= 1; --i) {
        if (p[i]) {
            cout << i << endl;
            exit(0);
        }
    }
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
   if(a==b)
    cout<<"Draw";
   else if(a>b&&b!=1||a<b&&a==1)
    cout<<"Alice";
   else if(a>b&&b==1||a<b&&a!=1)
    cout<<"Bob";

    return 0;
}


Measured memory_bytes: 3636
def funct(a, b, v, w, t):
    x = abs(a - b)
    s = v - w
    if(s <= 0): return False
    else:
        if(x // (v - w) < t or (x % (v - w) == 0 and x // (v - w) <= t)):
            return True
        else:   return False    
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if(funct(a, b, v, w, t)):
    print('YES')
else:
    print('NO')

Measured memory_bytes: 9212
local h, w = io.read("*n", "*n", "*l")
local t = {}
local s_sharp = string.byte("#")
for i = 1, h do
  local s = io.read()
  for j = 1, w do
    local idx = (i - 1) * w + j
    t[idx] = s:byte(j) ~= s_sharp
  end
end
local score = {}
for i = 1, h * w do score[i] = 0 end
local len = 0
local function func(idx)
  score[idx] = score[idx] + len
  if t[idx] then len = len + 1
  else len = 0
  end
end
for i = 1, h do
  len = 0
  for j = 1, w do
    func((i - 1) * w + j)
  end
end
for i = 1, h do
  len = 0
  for j = w, 1, -1 do
    func((i - 1) * w + j)
  end
end
for j = 1, w do
  len = 0
  for i = 1, h do
    func((i - 1) * w + j)
  end
end
for j = 1, w do
  len = 0
  for i = h, 1, -1 do
    func((i - 1) * w + j)
  end
end
local ret = 0
local mma = math.max
for i = 1, h * w do
  if t[i] then
    ret = mma(ret, score[i])
  end
end
print(ret + 1)


Measured memory_bytes: 70092
def main():
    X = int(input())
    # 500円をp個、5円をq個とすると。500p+5q=Xが成り立ち、ansは1000p+5qになる
    p = int(X/500)
    q = int((X-p*500)/5)
    ans = 1000*p + 5*q
    print(ans)

main()


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

public class Hello
{
    private const int MOD_N = 1000000000 + 7;

    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());

        Console.WriteLine((n - 2) * 180);
    }

    private static int Comb(int m, int n)
    {
        var t = m - n;
        if (n > t)
            n = t;

        long numerator = 1;
        for (int i = 0; i < n; ++i)
        {
            numerator *= m - i;
            numerator %= MOD_N;
        }
        long denominator = 1;
        for (; n != 0; --n)
        {
            denominator *= n;
            denominator %= MOD_N;
        }

        var inv_denominator = ModInv((int)denominator, MOD_N);
        var ret = (int)(numerator * inv_denominator % MOD_N);

        return ret >= 0 ? ret : ret + MOD_N;
    }

    private static int ModInv(int a, int m)
    {
        int b = m, x = 1, y = 0;
        while (b != 0)
        {
            var t = a / b;
            a -= t * b;
            Swap(ref a, ref b);
            x -= t * y;
            Swap(ref x, ref y);
        }
        x %= m;
        return x >= 0 ? x : x + m;
    }

    private static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 2e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


ll n, a, b[N];

void solve()
{
    cin >> n;
    cin >> a; b[0] = a;
    for (int i=1; i<n; i++) {
        cin >> b[i];
        a=a^b[i];
    }
    for (int i=0; i<n; i++) {
        sout(a^b[i]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

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


struct unionFind {
    vector<int> parent;
    unionFind(int n): parent(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    };

    int root(int x) {
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) parent[y] = x;
    }

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int a, b;
    cin >> a >> b;
    int s = max(floor(a/0.08), floor(b/0.1));
    int e = min(floor((a+1)/0.08), floor((b+1)/0.1));
    for (int i = s; i < e; i++) {
        if (floor(i*0.08) == a && floor(i*0.1) == b) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;





    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // Educational DP Contest F - LCS
  // dp[i][j]:文字列sのi文字目、文字列tのj文字目を見たときの最長共通部分文字列
  // 状態遷移（以下のうちの最大値）
  // dp[i][j] = dp[i-1][j] : 文字列sのi文字目が最長共通部分文字列ではない場合
  // dp[i][j] = dp[i][j-1] : 文字列tのj文字目が最長共通部分文字列ではない場合
  // dp[i][j] = dp[i-1][j-1] + (s[i-1]==t[j-1]) : 文字列sのi文字目、文字列tのj文字目が最長共通部分文字列の場合
  // 復元方法（dpが更新された部分を探索していく方法）
  // dpテーブルをNから1までと、Mから1までを順に見ていく
  // Nのときのdpの値とN-1のときのdpの値が異なるものを探索
  // そのときMのdpの値とM-1のdpの値が異なれば、文字列sのN文字目、文字列tのM文字目が最長共通部分文字列の1文字
  string s, t;
  cin >> s >> t;
  int N = s.size(), M = t.size();
  vector<vector<int> > dp(N+1, vector<int>(M+1, 0));
  
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= M; j++){
      chmax(dp[i][j], dp[i-1][j]);
      chmax(dp[i][j], dp[i][j-1]);
      chmax(dp[i][j], dp[i-1][j-1] + (s.at(i-1) == t.at(j-1)));
    }
  }
  string ans;
  while(N > 0 && M > 0){
    if(dp[N][M] == dp[N-1][M]){
      N--;
    }else if(dp[N][M] == dp[N][M-1]){
      M--;
    }else{
      ans = s.at(N-1) + ans;
      N--;
      M--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 35584
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char c = s.charAt(0);

		String nextWeather = c == 'S' ? "Cloudy"
							: c == 'C' ? "Rainy"
							: "Sunny";
		System.out.println(nextWeather);

		sc.close();
	}
}


Measured memory_bytes: 19924
from collections import deque

def main():
    n, m = map(int, input().split())
    route = [[] for _ in range(n+1)]
    ans = [None]*(n+1)
    for _ in range(m):
        a, b = map(int, input().split())
        route[a].append(b)
        route[b].append(a)
    q = deque([1])
    while q:
        parent = q.pop()
        children = route[parent]
        for child in children:
            if ans[child] is None:
                ans[child] = parent
                q.appendleft(child)
    print("Yes")
    print("\n".join(list(map(str, ans[2:]))))

if __name__ == "__main__":
    main()

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


int n;

char next_animal(string& a, string& b, int i){
  if(b[i]=='S'){
    if(b[i-1]=='S'){
      if(a[i%n]=='o') return 'S';
      else return 'W';
    }else{
      if(a[i%n]=='o') return 'W';
      else return 'S';
    }
  }else{
    if(b[i-1]=='S'){
      if(a[i%n]=='o') return 'W';
      else return 'S';
    }else{
      if(a[i%n]=='o') return 'S';
      else return 'W';
    }
  }
}

bool res(string& a, int m){
  rep(i,m){
    if(a[i]!=a[n+i]) return false;
  }
  return true;
}

signed main(){
  cin>>n;
  string s; cin>>s;
  int ans = 0;

  string a,b,c,d;
  a = "SS", b = "SW", c = "WS", d = "WW";
  reps(i,n+5){
    a.PB(next_animal(s,a,i));
    b.PB(next_animal(s,b,i));
    c.PB(next_animal(s,c,i));
    d.PB(next_animal(s,d,i));
  }
  if(res(a,5)){
    rep(i,n){
      cout<<a[i];
    }
  } 
  else if(res(b,5)){
    rep(i,n){ 
      cout<<b[i];

    }
  } 
  else if(res(c,5)){
     rep(i,n) {
      cout<<c[i];
     }
  }
  else if(res(d,5)){
    rep(i,n){
      cout<<d[i];
    }
  }  
  else {
    cout << -1;
  }

  cout << endl;

  return 0;
}


Measured memory_bytes: 1152
#include<stdio.h>
int main(void)
{
	int akito = 0, bokusarmurase = 0, i;
	char mozi[101] = { '0' };
	while (1)
	{
		scanf("%s", mozi);
		if (mozi[0] == '0')
			break;
		for (i = 1; i < 100; i++)
		{
			if (mozi[i] == 'A')
				akito++;
			else if (mozi[i] == 'B')
				bokusarmurase++;
			else if (mozi[i] == '0')
				break;
		}
		if (akito > bokusarmurase)
			printf("%d %d\n", akito + 1, bokusarmurase);
		else
			printf("%d %d\n", akito, bokusarmurase + 1);
		for (i = 0; i < 100; i++)
		{
			mozi[i] = '0';
		}
		akito = 0;
		bokusarmurase = 0;
	}
	return 0;
}

Measured memory_bytes: 536
#include<bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    int N; cin >> N;
    vector<ll> L(86);
    L[0] = 2;
    L[1] = 1;
    for(int i=2; i <= N; i++){
        L[i] = L[i-1] + L[i-2];  
    }
    cout << L[N]; 

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main(){
    // 引数の受け取り
    int a,b,c,d;
    
    scanf("%d %d %d %d",&a,&b,&c,&d);
        
    printf("%d",max(a*b,c*d));

    return 0;
}


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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  //cout << n << endl;
  int x=0, y=0, z=0;
  for(int i=0;i<(n-1)/4;i++){
    if(s[i]!=s[(n-1)/2-i-1]){
      x=1;
    }
  }
  for(int i=0;i<(n-1)/4;i++){
    if(s[i+(n+1)/2]!=s[n-1-i]){
      y=1;
    }
  }
  for(int i=0;i<(n-1)/2;i++){
    if(s[i]!=s[n-1-i]){
      z=1;
    }
  }
  if(x==0&&y==0&&z==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main() {
    int r; cin >> r;
    printf("%.10lf\n", 2*M_PI*r);

}

Measured memory_bytes: 3768
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a = input()
b = input()

print("YES" if a == b[::-1] else "NO")

Measured memory_bytes: 5148
#include<iostream>
using namespace std;
int main()
{
  int R;
  cin >> R;
  if(R >= 0 && R < 1200)
  {
    cout << "ABC";
  }else if (R < 2800)
  {
    cout << "ARC";
  }else if(R <= 4208)
  {
    cout << "AGC";
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld long double
#define ff first
#define ss second
const ll mod =   1e9 + 7 ;
ll multiply(ll a, ll b ){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
void solve(){
    int n ;
    cin >> n ;
    vector < ll > a(n) ;
    ll cost = 1000 ;
    for( int i = 0 ; i < n ; i++) cin >> a[i] ;
    for( int i = 1 ; i < n ; i++){
        if(a[i]>a[i-1]){
            ll sell = cost/a[i-1];
            ll r = cost - a[i-1]*sell;
            cost = r + sell*a[i] ;
        }
    }
    cout << cost ;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1 ;
    // cin >> t ;
    while(t--){
        solve( );
    }
}


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

int n, W, ans, base, w[101], v[101], dp[101][501];
bool can[101][501];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> W;
	for(int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
		if(i == 1) base = w[i];
		w[i] -= base-1;
	}
	can[0][0] = true;
	for(int i = 1; i <= n; i++) for(int j = n; j >= 1; j--) {
		for(int k = w[i]; k <= 500; k++) if(can[j-1][k-w[i]]) {
			dp[j][k] = max(dp[j-1][k-w[i]]+v[i], dp[j][k]);
			can[j][k] = true;
		}
		if(1ll*j*(base-1) > W) continue;
		for(int k = 0; k <= min(500, W - j*(base-1)); k++) ans = max(dp[j][k], ans);
	}
	cout << ans;
}


Measured memory_bytes: 512
//by Top1
#include <bits/stdc++.h>
          
#define f first
#define s second
#define int long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <long, long>
#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define cerr cout
#define rev reverse
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define boost ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define nxtp next_permutation
#define pvtp prev_permutation
#define KZ return 
#define x1 x21212121
#define y1 y21212121
#define sqr(x) x * x 
      
const int inf = (1e9) + 1;
const int mod = 479001599;
const int maxn = 1e6 + 111;
        
using namespace std;          

int n, a[maxn], b[5][5];
bool was[maxn];

void solve(){           
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++)
			cin >> b[i][j];

	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
		was[a[i]] = true;
	}

	for (int i = 1; i <= 3; i++){
		int x = 0;
		for (int j = 1; j <= 3; j++)
			x += was[b[i][j]];
		if (x == 3){
			cout << "Yes";
			return;
		}
		x = 0;
		for (int j = 1; j <= 3; j++)
			x += was[b[j][i]];
		if (x == 3){
			cout << "Yes";
			return;
		}
	}

	int x = 0;

	for (int i = 1; i <= 3; i++)
		x += was[b[i][i]];

	if (x == 3){
		cout << "Yes";
		return;
	}

	x = 0;

	for (int i = 1; i <= 3; i++)
		x += was[b[3 - i + 1][i]];

	if (x == 3)
		cout << "Yes";
	else
		cout << "No";
}                              
      
main(){
    boost;
    
    int q = 1;
 
    //cin >> q;
    
    while (q--){
        solve();
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

int main(){
	ll n;
	cin>>n;
	ll arr[n+1];
	for(ll i=0;i<n;i++){
		cin>>arr[i];
	}
	ll dp[n+1];
	memset(dp,0,sizeof(dp));
	//for(ll i=0;i<n;i++){
	//	dp[i]
	//}
	dp[0]=0;
	for(ll i=1;i<n;i++){
		//if(i>=1){
			dp[i]=dp[i-1]+abs(arr[i]-arr[i-1]);
	//	}
		if(i>=2){
			dp[i]=min(dp[i],dp[i-2]+abs(arr[i]-arr[i-2]));
		}
	//	cout<<dp[i]<<' ';
	}
	//cout<<'\n';
	cout<<dp[n-1];
	
}

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

using namespace std;

typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

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

    ll divC = B / C - (A-1) / C;
    ll divD = B / D - (A-1) / D;
    ll l = lcm(C, D);
    ll divLCM = B / l - (A-1) / l;

    ll ans = B - A + 1 - divC - divD + divLCM;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import heapq

X, Y, A, B, C= list(map(int, input().split()))
P = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
heapq.heapify(P)
Q = list(map(int, input().split()))
Q.sort(reverse=True)
Q = Q[:Y]
heapq.heapify(Q)
R = list(map(int, input().split()))
R.sort(reverse=True)
for r in R:
    p_min = P[0]
    q_min = Q[0]
    if p_min <= q_min and p_min < r:
        heapq.heapreplace(P, r)
    elif q_min <= p_min and q_min < r:
        heapq.heapreplace(Q, r)
    else:
        break
print(sum(P) + sum(Q))

Measured memory_bytes: 105444
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

int N;
ll ans = 0;
pair<int, int> P[(int)1e5 + 1];

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> P[i].first;
        P[i].second = i;
    }

    sort(P + 1, P + 1 + N, greater<pair<int, int>>());

    set<int> st;
    for (int i = 1; i <= N; i++)
    {
        int a = 0, b = 0, c = N + 1, d = N + 1;
        set<int>::iterator it = st.lower_bound(P[i].second);
        // cout << P[i].first << " " << P[i].second << endl;
        if (it != st.begin())
        {
            b = *(--it);
            if (it != st.begin())
                a = *(--it);
        }

        it = st.lower_bound(P[i].second);
        if (it != st.end())
        {
            c = *(it++);
            if (it != st.end())
                d = *(it++);
        }

        // cout << a << " " << b << " " << c << " " << d << endl;
        ans += (1ll * (b - a) * (c - P[i].second) + 1ll * (d - c) * (P[i].second - b)) * P[i].first;

        st.insert(P[i].second);
    }
    cout << ans << endl;
    // system("pause");

}

Measured memory_bytes: 5760
//
// !!!WARNING!!!
// AUTO SUBMITTION TEST ALERT
// !!!WARNING!!!
//

#include <stdio.h>

// Euclidean Algorithm
int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

int main() {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", gcd(x, y));
    return 0;
}



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

typedef long long ll;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int x;
	cin >> x;
	if(x < 1200){
	    ANS("ABC");
	}else{
	    ANS("ARC");
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int d,i,s;
    while(scanf("%d",&d)!=EOF)
    {
        s=0;
        for(i=d;i<600;i+=d)
            s+=d*i*i;
        printf("%d\n",s);
    }
    return 0;
}

Measured memory_bytes: 596
N = int(input())
T =[0]*N
A =[0]*N
Cnt=[1]*N
Cnt_pre =1
for i in range(N):
	T[i],A[i] = map(int,input().split())

for i in range(1,N):
	Cnt_pre = Cnt[i-1]
	if T[i]<T[i-1]*Cnt_pre:
		if (T[i-1]*Cnt_pre)%T[i]==0:
			Cnt[i] = (T[i-1]*Cnt_pre)//T[i]
		else:Cnt[i]= (T[i-1]*Cnt_pre)//T[i] + 1
	if A[i]*Cnt[i]<A[i-1]*Cnt_pre:
		if (A[i-1]*Cnt_pre)%A[i]==0:
			Cnt[i]=(A[i-1]*Cnt_pre)//A[i]
		else:Cnt[i]=(A[i-1]*Cnt_pre)//A[i]+1
print(Cnt[N-1]*(T[N-1]+A[N-1]))  

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll inf = LONG_LONG_MIN / 2 - 1;
    ll n, w;
    cin >> n >> w;
    vector<vector<ll>> dp(n + 1, vector<ll>(w + 1, inf));
    dp[0][0] = 0;
    ll ans = 0;
    rep(i, n) {
        ll tv, tw;
        cin >> tv >> tw;
        rep(j, w + 1) {
            if (j < tw) {
                dp[i + 1][j] = dp[i][j];
            }
            else {
                if (dp[i][j - tw] == inf) {
                    dp[i + 1][j] = dp[i][j];
                }
                else {
                    dp[i + 1][j] = max(dp[i][j], dp[i][j - tw] + tv);
                }
                ans = max(ans, dp[i + 1][j]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 10672
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)
  {
    int s;
    cin>>s;
    a[i]=s;
  }
  sort(a.begin(),a.end());
  int count=1;
  for(int j =0;j<n-1;j++)
  {
    if(a[j]!=a[j+1])
    {
      count+=1;
    }
    else
    {
      continue;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
	//Fast IO class
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() 
        { 
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else {
        		br = new BufferedReader(new
                        InputStreamReader(System.in)); 
        	}
        } 
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }     
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception
    {
        FastReader sc=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
    	int test=1;
        while(test-->0) {
        	int n=sc.nextInt(),W=sc.nextInt();
        	long dp[]=new long[W+1];
        	for(int i=0;i<n;i++) {
        		int w=sc.nextInt(),v=sc.nextInt();
        		for(int j=W;j>=w;j--) {
        			dp[j]=Math.max(dp[j-w]+v, dp[j]);
        		}
        	}
        	out.println(dp[W]);
        }
        out.close();
    }
}

Measured memory_bytes: 23636
#include <cstdint>
#include <iostream>

using namespace std;

#define ARRAY_SIZE 100000
static uint64_t array[ARRAY_SIZE];

int32_t main()
{
  int64_t n, k;
  cin >> n >> k;

  for (uint32_t i = 0; i < n; i++) {
    uint64_t a, b;
    cin >> a >> b;
    array[a] += b;
  }

  int64_t count = k;
  for (uint32_t i = 1; true; i++) {
    count -= array[i];
    if (count <= 0) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 1024
N = int(input())
cards = list(map(int, input().split()))

alice = 0
bob = 0

for i in range(int(N/2) + 1):
	if len(cards) > 0:
		alice += max(cards)
		cards.remove(max(cards))
	if len(cards) > 0:
		bob += max(cards)
		cards.remove(max(cards))
	
print(alice - bob)
	
	
	

Measured memory_bytes: 9108
n = gets.chomp.to_i

i = 1

while i < n
    i += 1
    x = i

    if x % 3 == 0
        print " #{i}"
        next
    end

    x *= 10
    while (x /= 10) > 0
        if x % 10 == 3
            print " #{i}"
            break
        end
    end

end

puts ""

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int X; cin >> X;
  if(X >= 400 && X <= 599) {
    cout << 8 << endl;
  } else if(X >= 600 && X <= 799) {
    cout << 7 << endl;
  } else if(X >= 800 && X <= 999) {
    cout << 6 << endl;
  } else if(X >= 1000 && X <= 1199) {
    cout << 5 << endl;
  } else if(X >= 1200 && X <= 1399) {
    cout << 4 << endl;
  } else if(X >= 1400 && X <= 1599) {
    cout << 3 << endl;
  } else if(X >= 1600 && X <= 1799) {
    cout << 2 << endl;
  } else if(X >= 1800 && X <= 1999) {
    cout << 1 << endl;
  } 
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000011
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
 
int main(){
  int n;
  cin>>n;
  
  double val[n];
  double con=100000000.0;
  rep(i, n){
    double a;
    cin>>a;
    val[i]=a;}
  
  
  for(int j=0;j<=250;j++){
  sort(val, val+n);
  if(val[1]!=100000000.0){
    val[1]=(val[0]+val[1])/2;
    val[0]=100000000.0;}
    else{
      break;}
  }
  
  cout<<fixed;
std::cout << std::setprecision(6) <<val[0]<<endl; 
  return 0;
  
 
}

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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

int main() {
	int N;
	cin >> N;
	vector<int> s;
	for (int i = 0; i < N; i++) {
		int b;
		cin >> b;
		s.push_back(b);
	}
	sort(s.begin(), s.end());
	int k = 0;
	int b = 0;
	while (b != 1) {
		int c = 0;
		for (int i = 0; i < N; i++) {
			if (s[i] != 0) {
				k = s[i];
				c = i;
				if (i == N - 1) {
					b = 1;
				}
				break;
			}
		}
		for (int i = c + 1; i < N; i++) {
			s[i] = s[i] % k;
		}
		sort(s.begin(), s.end());
	}
	cout << k;
}


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

l = [None] * N

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

minX = min([e[0] for e in l])
minY = min([e[1] for e in l])
maxX = max([e[0] for e in l])
maxY = max([e[1] for e in l])

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

s0 = min([d([minX,minY], e) for e in l])
s1 = min([d([maxX,maxY], e) for e in l])
 
t0 = min([d([maxX,minY], e) for e in l])
t1 = min([d([minX,maxY], e) for e in l])
 

print(d([minX,minY], [maxX,maxY]) - min(s0+s1, t0+t1))






Measured memory_bytes: 53276
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(a%d==0 and b*(a/d)<c) 
	cout<<"No";
	if(a%d==0 and b*(a/d)>=c)
	cout<<"Yes";
	if(a%d!=0 and b*(a/d+1)<c)
	cout<<"No";
	if(a%d!=0 and b*(a/d+1)>=c)
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 3524
S,T = map(str,input().split())
A,B = map(int,input().split())
U = input()

if S == U:
    Snew = A-1
    Tnew = B
else:
    Snew = A
    Tnew = B-1
    
Snew = str(Snew) 
Tnew = str(Tnew)
Ans =Snew+" "+Tnew

print(Ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PL = pair<long long, long long>;
const int INF = 1001001007;
const int mod = 1000000007;

int main(){
    int n; cin >> n;
    double le = n * 25.0 / 27.0;
    double ri = (n+1) * 25.0 / 27.0;
    int l = le / 1;
    int r = ri / 1;
    l--; r++;
    bool t = true;
    repp(i,r+1,l){
        if (le <= i && i < ri){
            cout << i << endl;
            t = false;
            break;
        }
    }
    if (t) cout << ":(" << endl;
}

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

int main(){
    int n; cin >> n;
    vector<int> a(n+1), b(n);
    rep(i,n+1) cin >> a[i]; rep(i,n) cin >> b[i];
    ll ans = 0;
    rep(i,n) {
        if(b[i] >= a[i]){
            ans += a[i];
            b[i] -= a[i];
        }else{
            ans += b[i];
            b[i] = 0;
        }
        if(b[i] >= a[i+1]){
            ans += a[i+1];
            a[i+1] = 0;
        }else{
            ans += b[i];
            a[i+1] -= b[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4028
#include <stdio.h>
int main() {int N,a,b,c;for (scanf("%d",&N);N--;) {scanf("%d %d %d",&a,&b,&c);if ((a*a+b*b==c*c)||(a*a+c*c==b*b)||(b*b+c*c==a*a)) puts("YES"); else puts("NO");}return 0;}

Measured memory_bytes: 0
#include <stdio.h>
int main(void){
    int a, b, d, r;
    double f;
    scanf("%d" "%d", &a, &b);
    d = a/b;
    r = a-(b*d);
    f = (double)a / (double)b;
    printf("%d %d %f\n", d, r, f);
    return 0;
}



Measured memory_bytes: 2100