akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FastScanner fsc = new FastScanner();
        long h = fsc.nextInt();
        long w = fsc.nextInt();
        if (h == 1 || w == 1) {
            System.out.println(1);
        } else if (h % 2 == 0 || w % 2 == 0) {
            System.out.println(h * w / 2);
        } else {
            System.out.println((h - 1) * w / 2 + (w + 1) / 2);
        }
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


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

int main(int argc, char *argv[]){
  int n;
  while(std::cin >> n, n){
  vector<int> ice(10, 0);
  for (int i = 0; i < n; i++) {
    int tmp;
    std::cin >> tmp;
    ice[tmp]++;
  }
  for (int i = 0; i < 10; i++) {
    if(ice[i] == 0)std::cout << "-";
    for (int j = 0; j < ice[i]; j++) {
      std::cout << "*";
    }
    std::cout << std::endl;
  }
  }
  return 0;
}

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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define debug(x) cerr << (#x) << "is "<< x << "\n"

using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;

int32_t main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	string s;
	cin >> s;
	ll n=s.length();
	s+='x';
	ll i=0,c1=0,c2=0;
	ll ans=0;
	while(i<n){
		if(s[i]=='A'){
			while(i<n and s[i]=='A'){
				c1++;
				i++;
			}
			while(i<n and s[i]=='B' and s[i+1]=='C'){
				c2++;
				i+=2;
			}
			// cout << c1 << " " << c2 << "\n";
			ans=ans+c1*c2;
			c2=0;
			// cout << i << "\n";
		}
		else{
			i++;
			c1=0;
		}
		// cout << ans << "\n";
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 720
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str="";
		String[] sca=new String[3];
		for(int i=0; i<3; i++) {
			sca[i]="";
			sca[i]=(sc.next()).charAt(i)+"";
		}
		System.out.println(sca[0]+sca[1]+sca[2]);
	}
}

Measured memory_bytes: 23636
// author:  Harsh Nema
#include <bits/stdc++.h>
#define ll long long int
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 10000000000000;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

//ll modexp(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;
//}

//ll mulmod(ll a, ll b,ll m)
//{
//	return ((a % m) * (b % m)) % m;
// }

// ll sub_mod(ll a, ll b, ll m){
//    if (a >= b)
//        return a - b;
//    else
//        return m - b + a;
// }

// ll add_mod(ll a, ll b){
//    if (0 == b)
//        return a;

//    b = mod - b;
//    if (a >= b)
//        return a - b;
//    else
//        return mod - b + a;
// }

// ll gcd(ll a, ll b)
// {
// 	if (a == 0)
// 		return b;
// 	else
// 		return gcd(b % a, a);
// }

// ll modInv(ll a)
// {
//     ll g = gcd(a, mod);
//     if (g != 1)
//         return -1;
//     else
//         return modexp(a, mod-2, mod);
// }

int main()
{
	fastio;
    ll n=0;
    cin>>n;
    ll x=1;
    for(ll i=1;i*i<=n;++i){
      if(n%i==0){
        x=i;
    }
    }
    cout<<x+n/x-2;
    return 0;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
	val (n, w) = readLine()!!.split(" ").map { it.toInt() }
	val values_list = Array<MutableList<Int>>(4) { mutableListOf(Int.MAX_VALUE) }
	var base = 0
	for (i in 0..(n - 1)) {
		val (a, b) = readLine()!!.split(" ").map { it.toInt() }
		if (i == 0) {
			base = a
		}
		values_list[a - base].add(b)
	}
	val values = Array<IntArray>(4) { values_list[it].toIntArray() }
	for (arr in values) {
		arr.sort()
		arr.reverse()
		arr[0] = 0
		for (i in 1..(arr.size - 1)) {
			arr[i] += arr[i - 1]
		}
	}
	var ans = 0
	for (i in 0..Math.min(w / base, values[0].size - 1)) {
		val rest0 = w - i * base
		var sum0 = values[0][i]
		for (j in 0..Math.min(rest0 / (base + 1), values[1].size - 1)) {
			val rest1 = rest0 - j * (base + 1)
			val sum1 = sum0 + values[1][j]
			for (k in 0..Math.min(rest1 / (base + 2), values[2].size - 1)) {
				val rest2 = rest1 - k * (base + 2)
				val sum2 = sum1 + values[2][k]
				val sum = sum2 + values[3][Math.min(rest2 / (base + 3), values[3].size - 1)]
				ans = Math.max(sum, ans)
			}
		}
	}
	println(ans)
}


Measured memory_bytes: 37928
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

    int n,m;cin>>n>>m;
    LL x[n],y[m];
    LL INF=1000000007;

    REP(i,n)cin>>x[i];
    REP(i,m)cin>>y[i];
    LL sumx[n],sumy[m];
    fill_n(sumx,n,0);
    fill_n(sumy,m,0);
    sumx[n-1]=x[n-1];sumy[m-1]=y[m-1];
    REP(i,n-1)sumx[n-2-i]=(sumx[n-1-i]+x[n-2-i])%INF;
    REP(i,m-1)sumy[m-2-i]=(sumy[m-1-i]+y[m-2-i])%INF;

    LL sigmax=0;
    LL sigmay=0;

    REP(i,n){
        sigmax +=sumx[i]-x[i]*(n-i);
        sigmax%=INF;
    }
    REP(i,m){
        sigmay +=sumy[i]-y[i]*(m-i);
        sigmay%=INF;
    }
    LL ans=(sigmax*sigmay)%INF;
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		 //sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;
int main() {
    string S;   
    cin>>S;
    ll ans = 0;
    int N = S.size();
    bool pre_2 = false;
    S.push_back('.');
    for(int i = 0; i < N; ++i){
        if(S[i] == S[i+1]&&(!pre_2)){
            i++;
            ans++;
            pre_2 = true;
        }
        else{
            ans++;
            pre_2 = false;
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 640
n,m=gets.split.map(&:to_i)
l=Array.new(n+1) {[]}
m.times do
  x,y,z=gets.split.map(&:to_i)
  l[x] << y
  l[y] << x
end
v=[0]*(n+1)
c=0
1.upto(n) do |i|
  next if v[i]==1
  c+=1
  s=[i]
  while s!=[]
    z=[]
    s.each do |j|
      l[j].each do |lj|
        if v[lj]==0
          v[lj]=1
          z << lj
        end
      end
    end
    s=z.dup
  end
end
puts c


Measured memory_bytes: 27852
/*input
4 5
1 2
1 3
3 2
2 4
3 4
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int path[100001];
vector < int > adj[100001];
bool vis[100001];
int dp[100001];
void dfs(int v) {
    vis[v] = true;
    for (int u : adj[v]) {
        if (!vis[u]) dfs(u);
        dp[v] = max(dp[v], 1 + dp[u]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<=n;i++)
    {
    	dp[i]=0;
    }

    for(int i=0;i<m;i++)
    {
    	int x,y;
    	cin>>x>>y;
    	adj[x].push_back(y);
    }
 	for(int i=0;i<=n;i++)
 	{
 		vis[i]=false;
 	}
    for(int i=1;i<=n;i++)
    {
    	if(!vis[i])
    		{
    		
    			dfs(i);
    		}
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
    	
    	ans=max(ans,dp[i]);
    }
    cout<<ans<<'\n';

}

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

void solve(){
	
	ll x,k,d ;
	cin>>x>>k>>d ;

	x=abs(x) ;

	ll ans=0 ;
	if(x/d-k>0){
		ans=x-k*d ;
	}
	else{

		ll e=x/d ;
		k-=e ;
		x-=e*d ;

		if(k%2==1)
			x=abs(x-d) ;
		ans=x ;

	}
	
	cout<<ans ;

}

int main(){
	
	int y ;

	y=1 ;
	//cin>>y ;

	while(y--)
	{	
		solve() ;
	}

}

Measured memory_bytes: 3640
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*
ll limit = 1e+9;
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int main(void){
  long N;
  cin >> N;
  priority_queue<long> a;
  long A;
  rep(i, N) {
    cin >> A;
    a.push(A);
  }
  long tmp_a, tmp_b;
  long ans= 0, count = 1;
  
  while(!a.empty()){
    tmp_a = a.top();
    a.pop();
    if (a.empty()) tmp_b = -1;
    else tmp_b = a.top();
    if (tmp_a == tmp_b) {
      count++;
    } else {
      //cout<< "hey" << endl;
      if (count%2 != 0) ans+= 1;
      count = 1;
    }
  }
   cout << ans << endl;
}


Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{    
    int n,x;
    cin >> n >> x;
    vector<int> m(n);
    rep(i,n) cin >> m[i];

    int min_m = *min_element(m.begin(),m.end());
    int sum_m = accumulate(m.begin(),m.end(),0);

    int cnt = n + (x-sum_m)/min_m;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,X,Y;
  cin>>A>>B>>C>>X>>Y;
  int l=min(X,Y), h=max(X,Y);
  vector<int> P={
    A*X+B*Y,
    2*C*X+max(0,Y-X)*B,
    max(0,X-Y)*A+2*C*Y,
  };
  cout<<min(P[0],min(P[1],P[2]))<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl "\n"
const int MAX= 100005 ;
const long long mod = 1.0e9+7;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t;
    t=1;
    while(t--)
    {
        int n,m,i,x,y,z;
        cin>>n>>m;
        if((m%2)==1){
            cout<<"No"<<endl;
            return 0;
        }
        m=m/2;
        y=m-n;
        x=2*n-m;
        if(x>=0 && y>=0)
            cout<<"Yes"<<endl;
        else
        {
            cout<<"No"<<endl;
        }
        
    }
    return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
char s[200],t[200];
int main(){
	int a=0,b=0;
	int n;
	scanf("%d",&n);
	while(n--){
		scanf(" %s%s",s,t);
		int flag=strcmp(s,t);
		if(flag>0)a+=3;
		if(flag<0)b+=3;
		if(flag==0)a++,b++;
	}
	printf("%d %d\n",a,b);
}


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

template<typename T> class CumulativeSum2D{
    public:
        vector<vector<T>> sum;
        
        CumulativeSum2D(int h, int w);
        void add(int x, int y, T v);
        void build();
        T get_rectangle(int sx, int sy, int gx, int gy);

        void build_row();
        void build_column();
        T get(int i, int j);
};

template<typename T> CumulativeSum2D<T>::CumulativeSum2D(int h, int w){
    sum = vector<vector<T>>(h + 1, vector<T>(w + 1, 0));
}

template<typename T> void CumulativeSum2D<T>::add(int x, int y, T v){
    sum[x + 1][y + 1] += v;
}

template<typename T> void CumulativeSum2D<T>::build(){
    for (int i = 1; i < sum.size(); i++){
        for (int j = 1; j < sum[i].size(); j++){
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}

template<typename T> void CumulativeSum2D<T>::build_row(){
    for (int i = 1; i < sum.size(); i++){
        for (int j = 1; j < sum[i].size(); j++){
            sum[i][j] += sum[i][j - 1];
        }
    }
}

template<typename T> void CumulativeSum2D<T>::build_column(){
    for (int i = 1; i < sum.size(); i++){
        for (int j = 1; j < sum[i].size(); j++){
            sum[i][j] += sum[i - 1][j];
        }
    }
}

template<typename T> T CumulativeSum2D<T>::get_rectangle(int sx, int sy, int gx, int gy){
    return sum[gx + 1][gy + 1] - sum[sx][gy + 1] - sum[gx + 1][sy] + sum[sx][sy];
}

template<typename T> T CumulativeSum2D<T>::get(int i, int j){
    return sum[i + 1][j + 1];
}

const int Max = 100010;

int main(){
    int n, ch;
    cin >> n >> ch;
    CumulativeSum2D<int> cs(ch, Max);
    for (int i = 0; i < n; i++){
        int s, t, c;
        cin >> s >> t >> c;
        cs.add(c - 1, s - 1, 1);
        cs.add(c - 1, t, -1);
    }

    cs.build_row();
    for (int i = 0; i < ch; i++){
        for (int j = 0; j < Max; j++){
            if (cs.get(i, j) >= 2) cs.add(i, j, -1);
        }
    }

    cs.build_column();
    int ans = 0;
    for (int i = 1; i < Max; i++){
        ans = max(ans, cs.get(ch - 1, i));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12800
#include<stdio.h>
#include<string.h>
int hantei(char A[],char C[],int a);
int main(){
  int a,i,j,flag,minj,c;
  char A[36][3],B[36][3],Z[1][3];
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%s",A[i]);
    strcpy(B[i],A[i]);
  }
  flag = 1;
    while (flag == 1){
      flag = 0;
      for (j=a-1;j>=1;j--){
        if (A[j][1] < A[j-1][1]){
          strcpy(Z[0],A[j]);
          strcpy(A[j],A[j-1]);
          strcpy(A[j-1],Z[0]);
        flag = 1;
        }
	  }
    }
    for(i=0;i<a;i++){
      if(i!=a-1)printf("%s ",A[i]);
      else printf("%s\n",A[i]);
    }
  printf("Stable\n");
 for (i=0;i<a;i++){
    minj = i;
    for (j=i;j<=a-1;j++){
      if (B[j][1] < B[minj][1]){
        minj = j;
      }
    }
    if(minj!=i){
         strcpy(Z[0],B[i]);
          strcpy(B[i],B[minj]);
          strcpy(B[minj],Z[0]);
    }
 }
   for(i=0;i<a;i++){
    if(i!=a-1)printf("%s ",B[i]);
    else printf("%s\n",B[i]);
}
   c=hantei(B[0],A[0],a);
   if(c==1)printf("Stable\n");
    else printf("Not stable\n");  
}
int hantei(char A[],char C[],int a){
  int i,j,c;
  for(i=0;i<a;i++){
    c=strcmp(&A[i*3],&C[3*i]);
    if(c!=0)return 0;
  }
  return 1;
}



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

int main() {
  int n;
  cin >> n;
  vector<ll> cnt(100001, 0);
  rep(i,n) {
    int a;
    cin >> a;
    cnt[a]++;
  }
  ll tot = 0;
  rep(i,100001) tot += i*cnt[i];

  int q;
  cin >> q;
  rep(i,q) {
    int b, c;
    cin >> b >> c;
    tot -= b*cnt[b];
    tot -= c*cnt[c];
    cnt[c] += cnt[b]; 
    cnt[b] = 0;
    tot += b*cnt[b];
    tot += c*cnt[c];
    cout << tot << endl;
  }
  return 0;
}

Measured memory_bytes: 3988
#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;
using ll = long long;
using ld = long double;
using vvll = vector<ll, vector<ll> >;
using vll = vector<ll> ;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio(); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

bool match(string & s, int ind, string toMatch) {
    for(int j = (int)toMatch.length()-1;j >= 0;j --) {
        if(ind < 0) {
            return false;
        }
        if(s[ind --] != toMatch[j]) {
            return false;
        }
    }
    return true;
}

void UPDATE(string & s, int ind, string toMatch) {
    for(int i = (int)toMatch.length()-1;i >= 0;i --) {
        s[ind --] = toMatch[i];
    }
}

int main() {
    fastio();

    string s;
    cin >> s;
    long long N, cnt = 0;
    N = (int)s.length();
    ll A = 0;
    bool B = false;
    for(int i = 0;i < N;i ++) {
        if(s[i] == 'A') {
            if(B == true) {
                A = 0;
            }
            A ++;
            B = false;
        } else if(s[i] == 'C') {
            if(i > 0 && s[i-1] =='B') {
                cnt += A;  
                if(A > 0)
                    s[i] = 'A';
            } else {
                A = 0;
            }
            B = false;
        } else {
            if(i > 0 && s[i-1] == 'A') {
                // B = true;
            } else {
                A = 0;
            }
            B = true;
        }
    }
    cout << cnt ;
}

Measured memory_bytes: 720
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        C = [0]*2
        C[0] = 1
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            color = 1^W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = color
                    que.append(ne)
                    C[color] += 1
                else:
                    if color!=W[ne]:
                        return n*(n-1)//2
        rep = C[0]*C[1]
        return rep
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    ans = bfs(N,0,V) - M
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 27884
h,w,a,b=map(int,input().split())
fac=[0]*200001#iの階乗mod(1000000007)
inv=[0]*200001#iの逆元mod(1000000007)
fac[0]=1
ans=0
for i in range(1,200001):
    fac[i]=fac[i-1]*i%1000000007
inv[200000]=pow(fac[200000],1000000005,1000000007)
for i in range(199999,0,-1):
    inv[i]=(inv[i+1]*(i+1))%1000000007
    inv[0]=1
for i in range(h-a):
    if i==0:
        if h==1:
            x=1
        else:
            x=(fac[w-b+h-2
                   -i]*inv[w-1-b]*inv[h-1-i])%1000000007
    else:
        x=((fac[b-1+i]*inv[b-1]*inv[i])%1000000007)*((fac[w-b+h-2-i]*inv[w-b-1]*inv[h-1-i])%1000000007)
    ans=(ans+x)%1000000007
print(ans)


Measured memory_bytes: 24708
//参考：https://qiita.com/DaikiSuyama/items/9dba963ba74396b9b7fd
//インクルード(アルファベット順)
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define FIR first    //pairの一つ目の要素
#define SEC second   //pairの二つ目の要素

signed main()
{
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    ll ans;
    if (A + B > 2 * C)
    {
        ans = 2 * C * min(X, Y);
        ll dif = abs(X - Y);

        if (X > Y)
        {
            ans += A > 2 * C ? 2 * C * dif : A * dif;
        }
        else
        {
            ans += B > 2 * C ? 2 * C * dif : B * dif;
        }
    }
    else
    {
        ans = A * X + B * Y;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3616
//3 key, 0, 1, backspace

//only display 1 string / empty
//when launched, it'll be empty
//then
//if pressed:
//0 --> 0 muncul dikanan
//1 --> 1 muncul dikanan
//backspace --> kalo kosong, ya gaada, kalo ada, yg paling kanan keapus

//Sig launced the editor trs pencet2 key ini
//ada string, itu apa aja yg dia pencet
//0 -> 0, 1 -> 1, B -> backspace
//string yg muncul apa?

//panjang string max 10
//isinya 0,1,B
//output gaboleh empty

//input = string
//output = string akhirnya
//misal sample input
//01B0	-> 0 -> 01 -> 0 -> 00
//0BB1 -> 0 ->  ->  -> 1

#include <stdio.h>
#include <string.h>
int main(){
	char str[11];
	scanf("%s", &str);

	char keluar[11];

	int j = 0, i = 0;
	int len = strlen(str);

	while(len--)		//gantinya for biar pendek
	{
		if(str[j] == 'B')
		{
			if(i > 0)	//kalo dia bkn yg pertama gaada bedanya
			{
				i--;		//kalo bener kondisinya dia mundur 1 index
			}
			keluar[i]= ' ';		//trs diganti jadi kosong, jd kl mau isi bisa2 aja
			j++;	//lanjut
		}
		else
		{
			keluar[i] = str[j];	//isi keluar bernilai sama dengan str (idk biar copy?)
			i++;			//ok it works
			j++;
		}
	}
	
	keluar[i] = '\0';		//mentoknya dimana, nanti dipakein null terminator (kayak titik prinsipnya)
	printf("%s", keluar);
	return 0;
}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>l(n);
    rep(i,n){
        cin>>l[i];
    }
    sort(l.rbegin(),l.rend());
    int ans=0;
    rep(i,k){
        ans+=l[i];
    }
    cout<<ans<<endl;
}

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

map<ll,int> primeFact(ll n) {
	map<ll,int> r;
	for(ll i=2; i*i<=n; i++)
		while(n%i == 0) {
		r[i]++;
		n /= i;
		}
	if(n != 1)
		r[n] = 1;
	return r;
}

int main() {
	ll N,r=0;
	cin >> N;

	map<ll,int> m = primeFact(N);

	for(auto p : m) {
		int x = (int)sqrt(p.second*2);
		if(x*(x+1) > p.second*2)
			--x;
		r += x;
	}

	cout << r << endl;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
//#define INF (1LL<<31)-1
//#define MOD 998244353
#define MOD 1000000007

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int t=0;
    rep(i,0,m){
        int x;
        scanf("%d",&x);
        t+=x;
    }
    n-=t;
    if(n>=0)printf("%d",n);
    else printf("-1");
    
    
}

Measured memory_bytes: 3824
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <string>
#define ll long long
#define read(x) scanf("%d",&x);
#define readll(x) cin>>x;
#define FOR(x,a,b) for(int x=a;x<b;x++)
#define MP make_pair
#define PB push_back
#define pii pair<int,int>
#define readN(N,X) for(int i=0;i<N;i++) cin>>X[i];
#define pff pair<double,double>
#define MMOD 1000000007
using namespace std;

long long fastpow(long long a, long long b, long long MOD)
{
    long long x=1,y=a; 
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x=(x*y) % MOD;
        }
        y = (y*y) % MOD;
        b /= 2;
    }
    return x;
}

long long InverseEuler(long long n, long long MOD)
{
    return fastpow(n,MOD-2,MOD);
}
 
long long f[300000];
bool init;
long long W[300000];
long long C(long long n, long long r, long long MOD)
{
    if (!init){
        init=1;
        f[0]=1;
        for (int i=1; i<300000;i++)
            f[i]= (f[i-1]*i) % MOD;
        
    }
    return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}


long long getprob(int A, int B, int N) {
    long long invA = A * InverseEuler(A + B, MMOD) % MMOD;
    long long invB = B * InverseEuler(A + B, MMOD) % MMOD;

	long long cA = 1;
	long long cB = 1;
	for (int i=0; i < N;i++) {
      cA = (cA * invA) % MMOD;
	}
	// cout<<cA<<endl;
    long long totCh = 0;
	for (int j=0;j < N;j++) {
      totCh += (((cA * cB) % MMOD) * W[j]) % MMOD * (N + j);
      // cout<<j<<" : "<<C(N - 1 + j, j, MMOD)<<" - "<<W[j]<<" | "<<cA<<" "<<cB<<endl;
      totCh %= MMOD;
      // cout<<totCh<<endl;
      cB = (cB * invB) % MMOD;

	}
	return (totCh) % MMOD;
}

void solve() {
	//cout<<C(100,0, 1000000007)<<endl;
  int N,A,B,Co;
  
  cin>>N>>A>>B>>Co;
  for (int i=0;i<= N;i++){
  	W[i] = C(N - 1 + i, i, MMOD);
  }
  long long invC = (100 - Co) * InverseEuler(100, MMOD) % MMOD;
  // A win
  cout<<(((getprob(A, B, N) + getprob(B, A, N) ) % MMOD) * InverseEuler(invC, MMOD)) % MMOD <<endl;
}
int main(){
  ios_base::sync_with_stdio(false);
  solve();
}

// 45 45 10





Measured memory_bytes: 3712
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
using namespace std;
int H, W;
char A[100][100];
vector<int> remove_hs, remove_ws; // 消す行と列
int main() {
  cin.sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> H >> W;
  rep(i, H) rep(j, W) cin >> A[i][j];
  
  // 縦の操作
  int cnt;
  rep(i, H) {
    cnt = 0;
    rep(j, W) {
      if (A[i][j] == '.') cnt++;
      else break; 
    }
    if (cnt == W) remove_hs.push_back(i);
  }
  // 横の操作
  rep(i, W) {
    cnt = 0;
    rep(j, H) {
      if (A[j][i] == '.') cnt++;
      else break; 
    }
    if (cnt == H) remove_ws.push_back(i);
  }
  int h_idx = 0;
  int w_idx = 0;
  rep(i, H) {
    if (remove_hs.size() > 0 && i == remove_hs[h_idx]) {
      h_idx++;
      continue;
    }
    rep(j, W) {
      if (remove_ws.size() > 0 && j == remove_ws[w_idx]) {
        w_idx++;
        continue;
      }
      cout << A[i][j];
    }
    w_idx = 0;
    cout << "\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int a[300000];
int c[300000];
int rc[300001];
int ans[300001];

int main() {
	int i;
	
	cin >> n;
	rep(i, n) { cin >> a[i]; a[i]--; c[a[i]]++; }
	sort(c, c + n);
	rep(i, n) { rc[i + 1] = rc[i] + c[i]; }

	//t回操作できるようなkの最大値を求めて、ほげほげ
	//d[i] = min(c[i], t)とおくとき、Σd[i] >= ktを満たす最大のk
	int k = 1;
	for (int t = n; t >= 1; t--) {
		int p = lower_bound(c, c + n, t) - c;
		int s = (n - p) * t + rc[p];
		int kmax = s / t;
		if (kmax > n) kmax = n;
		for (; k <= kmax; k++) ans[k] = t;
	}
	
	for (i = 1; i <= n; i++) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 5504
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Data.Char
import Control.Monad

makeUF n = (VU.unsafeThaw $ VU.generate n id) >>= return

root x par = do
    r <- VUM.read par x
    if x == r
        then return x
        else do
            newr <- root r par
            VUM.write par x newr
            return newr

same x y par = do
    rx <- root x par
    ry <- root y par
    return $ rx == ry

unite x y par = do
    x' <- root x par
    y' <- root y par
    when (x' /= y') $ VUM.write par x' y'

toTuple bs =
    let
        Just (a, bs') = B.readInt bs
        Just (b, _) = B.readInt $ B.dropWhile isSpace bs'
    in
        (a, b)

main = do
    (n,m) <- toTuple <$> B.getLine 
    es <- VU.replicateM m (toTuple <$> B.getLine)
    let es' = VU.map (\(a,b) -> (a-1,b-1)) es
    xs <- forM [0..m-1] $ \i -> do
            par <- makeUF n
            forM_ [0..m-1] $ \j -> do 
                let (a,b) = es' VU.! j
                unless (i==j) $ unite a b par
            par' <- VU.unsafeFreeze par
            let res = VU.length $ VU.filter id $ VU.zipWith (==) par' (VU.fromList [0..n-1])
            return $ res > 1 
    print $ length [() | x<-xs, x]

Measured memory_bytes: 764
#input
T = []
N = int(raw_input())
T = raw_input().split()
M = int(raw_input())
PX = []
X = 0
T1 = []

#input matrix
for i in range(M):
    PX.append(map(int,raw_input().split()))


for j in range(M):
    #new time
    T1 = T[:]
    PJ = PX[j][0]
    XJ = PX[j][1]
    a = int(PJ)
    b = int(XJ)
    T1[a-1] = b
    
    #plus each time
    X = 0
    for k in range(N):
            X += int(T1[k])
    print X


Measured memory_bytes: 2568
import java.util.*;
import java.io.*;
class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String inp[]=br.readLine().split(" ");
		int n = Integer.parseInt(inp[0]);
		int k = Integer.parseInt(inp[1]);
		String in[]=br.readLine().split(" ");
		int arr[]=new int[n];
		for(int i=0;i<n;i++)
			arr[i]=Integer.parseInt(in[i]);
		int dp[]=new int[n];
		Arrays.fill(dp,1000000005);	
		dp[0]=0;	
		for(int i=0;i<n;i++){
			for(int j=1;j<=k;j++){
				if(i+j <n)
					dp[i+j]=Math.min(dp[i+j],dp[i]+Math.abs(arr[i]-arr[i+j]));
			}	

		}
		System.out.println(dp[n-1]);
	}
}

Measured memory_bytes: 44972
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(b<a) { a=b; return 1; } return 0; }

int main(){
  int h,w,n; cin >> h >> w >> n;
  vi a(n); rep(i,n) cin >> a[i];

  vector<vi> mp(h,vi(w));
  int i = -1, j = -1;
  int add = -1;
  int now = 1;
  int count = 0;
  rep(cnt,h*w){
    if(cnt % w == 0){ add *= -1; i++; j += add; }
    mp[i][j] = now;
    j += add;
    count++;
    if(count == a[now-1]){ now++; count = 0; }
  }
  rep(i,h){
    rep(j,w){
      cout << mp[i][j] << " ";
    }
    cout << endl;
  }
  cout << "\n";
  return 0;
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  string s;cin>>s;
  vector<int> count(3,0);
  int i;
  rep(i,s.size())
  {
    count[s[i]-'a']++;
  }
  sort(all(count));
  if(count[2]-count[0]<2)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 512
N = int(input())
A = list(map(int, input().split()))

from collections import defaultdict
 
counter = defaultdict(int)
 
for i in range(N):
    counter[i+1] += A[i]

ans = sorted(counter.items(), key=lambda x: x[1])

for i in ans:
    print(i[0], end=" ")

Measured memory_bytes: 29252
soten_set=[]
soten=list(map(int,input().split()))

while soten[0]!=-1 or soten[1]!=-1 or soten[2]!=-1:
    soten_set.append(soten)
    soten=list(map(int,input().split()))

for i in range(len(soten_set)):
    m=soten_set[i][0]
    f=soten_set[i][1]
    r=soten_set[i][2]

    if m==-1 or f==-1:
        print("F")
    elif m+f>=80:
        print("A")
    elif m+f>=65:
        print("B")
    elif m+f>=50:
        print("C")
    elif m+f>=30:
        if r>=50:
            print("C")
        else:
            print("D")
    elif m+f<30:
        print("F")



Measured memory_bytes: 5596
n=int(input())
s=input()
q=int(input())
k=list(map(int,input().split()))
for i in range(q):
  curr=k[i]
  dcount=0
  dmcount=0
  mcount=0
  ans=0
  for j in range(n):
    if j>=curr:
      if s[j-curr]=='D':
        dcount-=1
        dmcount-=mcount
      elif s[j-curr]=='M':
        mcount-=1
    if s[j]=='D':
      dcount+=1
    elif s[j]=='M':
      mcount+=1
      dmcount+=dcount
    elif s[j]=='C':
      ans+=dmcount
  print(ans)
      

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

using namespace std;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define ar array

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int > pii;
const ll MOD =1e9+7;


void solve(){
	int n, k; cin >> n>> k;
	for(int j=0; j < n; ++j){
		int x; cin >> x;
	}
	--k;
	int ans = (n-1)/k;
	if((n-1)%k)
		++ans;
	cout << ans;
}

int main(){
	int t=1;
	//cin >> t;
	while(t--){
		solve();
		cout <<'\n';
	}
}


Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int n = Integer.parseInt(br.readLine());
			for(int i=0;i<n;i++) {
				System.out.println(br.readLine().replace("Hoshino", "Hoshina"));
			}
		} catch (NumberFormatException e) {
		} catch (IOException e) {
		}
	}
}

Measured memory_bytes: 17156
# coding: utf-8
# Here your code !
n,k=map(int,input().split())

weight=[int(input()) for i in range(n)]
def binary_search(start,end):
    left = start
    right = end
    middle = 0
    while left < right:
        middle = (left + right)//2
        if simulate(middle,weight,k):
            right = middle
        else:
            left = middle + 1
    return left
 
def simulate(prb,wei,num):
    count = 1
    tmp = 0
    for j in wei:
        tmp += j
        if tmp > prb:
            tmp = j
            count += 1
            if count > num:
                return False
    return True
 
print(binary_search(max(weight), sum(weight)))

Measured memory_bytes: 11680
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        int odd = 0;
        float oddness;
        for (int i=1; i<=number ; i++) {
            if(i%2 == 1 ) {
                odd = odd + 1;
            }
        }
        oddness = (float) odd/number;
        System.out.printf("%.12f",oddness);
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
#include<math.h>
#include <stdio.h>
#include<vector>
#include<deque>
#include<stdlib.h>
//#include <algorithm>
#include<set>
#include <limits>
#include<iomanip>
#include<string>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define ll long long
#define d_5 100000
#define d9_7 1000000007
//非閉路グラフ、長さなし
int n;
struct graph{
  int num;
  vector<int> next;
  //bool past;//過去に通ったかを記録する
  int count;
  int depth;//頂点1からの距離
  int childnum;
  int result;
};
vector<graph> graphs;
void initgraph(int num){
  rep(i,num){
    graphs.push_back({i,{},0,0,0,0});
  }
  return;
}
void connectundire(int a,int b){
    graphs[a].next.push_back(b);
    graphs[b].next.push_back(a);
    return;
}
int search1(int num,int depth,int pre){//depthは何回再帰したか、という「最初の点からの深さ」
  graphs[num].depth=depth;
  int child=1;
  for(auto i:graphs[num].next){
    if(i==pre){
      continue;
    }
    child += search1(i,depth+1,num);
  }
  graphs[num].childnum=child;
  return child;
}
void search2(int num,int pre,int x){//depthは何回再帰したか、という「最初の点からの深さ」
  x+=graphs[num].count;
  graphs[num].result=x;
  for(auto i:graphs[num].next){
    if(i==pre){
      continue;
    }
    search2(i,num,x);
  }
  return;
}
void initcount(){
  rep(i,n){
    graphs[i].count=0;
  }
  return;
}
int main(void){
  int q;
  cin >> n >> q;
  int a,b;
  initgraph(n);
  graph root;
  rep(i,n-1){
    cin>> a >> b;
    a--;b--;
      connectundire(a,b);
  }
  search1(0,0,-1);
  int p,x;
  ll sum=0;
    initcount();
  rep(i,q){
    cin>>p>>x;
    p--;
    graphs[p].count+=x;
  }
  search2(0,-1,0);
  rep(i,n){
    cout<<graphs[i].result<<" ";
  }
	return 0;
}

Measured memory_bytes: 34792
#define _CRT_SECURE_NO_DEPRECATE
#include<bits/stdc++.h>
#define Rint register int
#define MP make_pair
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; // 注意必要时改类型
typedef vector<int> vi;
const int N = 1e5 + 5;
int n, m;
//f[j] 代表价值大于i所需的最小体积
//f[j] = min(f[j], f[j-v[i]] + w[i])
ll f[N], w[N], v[N];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
#ifdef _DEBUG
	int tt = clock();
	// freopen("in.txt", "r", stdin);
#endif 

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld%lld", &w[i], &v[i]); // height and value
	fill(f, f + N, (ll)1e13);
	f[0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = N; j >= v[i]; j--)
			f[j] = min(f[j], f[j - v[i]] + w[i]);

	int ans = 0;
	for (Rint i = 0; i < N; ++i) 
		if (f[i] <= m) ans = i;
	cout << ans;




#ifdef _DEBUG
	cerr << "\nTIME = " << clock() - tt << endl;
	tt = clock();
#endif

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <set>
#include <utility>

int h, w;
bool arr[11][11];
bool left[11][11];
int dx[] = {1, 0}, dy[] = {0, 1};

void func(int y, int x) {
    if(y == h && w == x) {
        return;
    }

    left[y][x] = true;
    for(int i = 0; i < 2; ++i) {
        int ny = y + dy[i], nx = x + dx[i];
        if(ny < 0 || ny >= h || nx < 0 || nx >= w) {
            continue;
        }

        if(arr[ny][nx] && !left[ny][nx]) {
            func(ny, nx);

            return;
        }
    }
}

int main() {
    std::cin >> h >> w;

    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            char c;
            std::cin >> c;

            arr[i][j] = c == '#';

        }
    }

    func(0, 0);

    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            if(arr[i][j] && !left[i][j]) {
                std::cout << "Impossible" << std::endl;

                return 0;
            }
        }
    }

    std::cout <<"Possible" << std::endl;

}

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

#define ll long long 
#define pll pair<ll,ll> 

vector<ll> V,D;
stack<ll> S;
ll ans=0;
void dfs(vector<ll> A[], ll x){
	V[x]=1;
	for(auto it:A[x]){
		if(!V[it]){
			dfs(A,it);
		}
	}
	S.push(x);
}

void dfs1(vector<ll> A[],ll x){
	V[x]=0;
	for(auto it:A[x]){
		if(V[it]){
			dfs1(A,it);
		}
		D[x]=max(D[x], D[it]+1);
		ans=max(ans,D[x]);
	}
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n,m;
	cin>>n>>m;
	V.resize(n+1,0);
	D.resize(n+1,0);
	vector<ll> A[n+1];
	for(ll i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		A[a].push_back(b);
	}
	for(ll i=1;i<=n;i++){
		if(!V[i])
			dfs(A,i);
	}
	vector<ll> B;
	while(!S.empty()){
		B.push_back(S.top());
		S.pop();
	}
	reverse(B.begin(), B.end());
	for(auto it:B){
		if(V[it])
			dfs1(A,it);
	}

	cout<<ans<<endl;

}


Measured memory_bytes: 14004
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define MOD 1000000007
#define mod 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 1e9+1e7

vector<vector<int> >v;
vector<bool>vis;
vector<int>plen;

int dfs(int u)
{
    vis[u]=true;
    int tans=0;
    for(int i=0;i<v[u].size();i++)
    {
        if(!vis[v[u][i]])
        {
            int t=dfs(v[u][i]);
            tans=max(tans,t);
        }
        else
            tans=max(tans,plen[v[u][i]]);
    }
    plen[u]=tans+1;
    return plen[u];
}

int main()
{
    fastio;
    int n,m;
    cin >> n >> m;
    v.resize(n);
    vis.resize(n,false);
    plen.resize(n,0);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        x-=1;y-=1;
        v[x].push_back(y);
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
            dfs(i);
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        //cout << plen[i] << " ";
        ans=max(ans,plen[i]);
    }
    //cout << endl;
    ans-=1;
    cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const ll INF = LLONG_MAX;
#define MAX_V 1010

ll V, E;
struct edge{int from; int to; ll cost;};
edge es[MAX_V*MAX_V];
ll d[MAX_V];

//sからの最短経路  O(NM)
void shortest_path(int s){
    for(int i = 0; i < V; i++) d[i] = INF;
    d[s] = 0;
    for(int j = 0; j < V-1; j++){
        bool update = false;
        for(int i = 0; i < E; i++){
            edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(!update) break;
    }
}

bool find_negative_loop(){
    memset(d, 0LL, sizeof(d));
    for(int i = 0; i < V; i++){
        for(int j = 0; j < E; j++){
            edge e = es[j];
            if(d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                if(i == V-1 && e.to == V-1) return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> V >> E;
    REP(i,E){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--,b--;
        es[i] = (edge){a, b, -c};
    }

    if(find_negative_loop()){
        cout << "inf" << endl;
        return 0;
    }

    shortest_path(0);
    cout << -d[V-1] << endl;

    return 0;
}


Measured memory_bytes: 256
//
//AtCoder Beginner Contest 176
//E
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    ll H,W,M;
    cin >> H >> W >> M;

    vector<int> hCnt(H, 0);
    vector<int> wCnt(W, 0);
    vector<pair<int, int>> mList;
    REP(m,M){
        int h, w;
        cin >> h >> w;
        h--;w--;
        hCnt[h]++;
        wCnt[w]++;
        mList.emplace_back(h,w);
    }
    int hMax = *max_element(ALL(hCnt));
    int wMax = *max_element(ALL(wCnt));

    int ans = hMax + wMax;

    ll pCnt = count(ALL(hCnt), hMax) * count(ALL(wCnt), wMax);

    ll pCheck = 0;
    REP(m, M){
        if (hCnt[mList[m].first] + wCnt[mList[m].second]==ans) pCheck++;
    }
    if (pCnt==pCheck) cout << ans-1 << endl;
    else cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 9796
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int A,B,ans=0;
  cin>>A>>B;
  for(int i=0;i<2;i++){
  if(A>=B){
  	ans+=A;
    A--;
  }else if(A<B){
  	ans+=B;
    B--;
  }
  }
  cout<<ans<<endl;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  bool flag = false;
  if(abs(c - a) <= d) flag = true;
  if(abs(c - b) <= d && abs(b - a) <= d) flag = true;
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.numeric;
import std.stdio;
import std.string;

void main()
{
    string s = readln.chomp;
    string t = readln.chomp;
    for (long diff = 0; diff < s.length; ++diff)
    {
        char[] n;
        n.length = s.length;
        for (long i = 0; i < s.length; ++i)
        {
            long d = i + diff;
            if (s.length <= d)
            {
                d %= s.length;
            }
            n[i] = s[d];
        }
        if (n == t)
        {
            writeln("Yes");
            return;
        }
    }
    writeln("No");
}


Measured memory_bytes: 256