akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define VIN(v) for(auto&elem_: (v) )cin>>elem_
#define VOUT(v, sep) for(_loop_int idx=0; idx<(_loop_int)v.size(); idx++) {cout<<v[idx]; if(idx<(_loop_int)v.size()-1) cout<<sep;} cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(debugidx,v.size())cout<<" "<<v[debugidx];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(debugidx,n)cout<<" "<<v[debugidx];cout<<endl

const ll MOD = 1000000007ll;
const int IINF = numeric_limits<int>::max()/2-1;
const ll LINF = numeric_limits<ll>::max()/2-1;

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

//vector<ll> dp;
ll n,m,k;

// void dfs(int i, int a,int b){

//     if(dp)
// }
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>k;

    vl a(n);
    vl b(m);
    VIN(a);
    VIN(b);

    vl csa(n+2);
    vl csb(m+2);
    REP(i,n) csa[i+1] = csa[i]+a[i];
    REP(i,m) csb[i+1] = csb[i]+b[i];
    csa[n+1] = LINF;
    csb[m+1] = LINF;
    
    int ans = 0;
    REP(i,n+1){
        if(csa[i]>k) continue;

        int ok = 0, ng = m+1;
        while (abs(ok-ng) > 1) {
            int mid = (ok + ng) / 2;
            if (csa[i]+csb[mid] <= k) ok = mid;
            else ng = mid;
        }

        chmax(ans,i+ok);

    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9532
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,h; cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	if(n == 25)
		cout << "Christmas";
	else if(n == 24)
		cout << "Christmas Eve";
	else if(n == 23)
		cout << "Christmas Eve Eve";
	else
		cout << "Christmas Eve Eve Eve";
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<String, Integer> words = new HashMap<String, Integer>();

		String line = null;
		try {
			line = br.readLine();
				line = line.trim();

				String[] splitedLine = line.split(" ");
				String longest = "", most = null;
				int max = 0;
				for(String word : splitedLine){
	        		if(words.containsKey(word) == true){
	        			words.put(word, words.get(word) + 1);
	        			max = max < words.get(word) ?  words.get(word) : max;
	        		} else {
	        			words.put(word, 1);
	        		}
	        	}

				for(String key : words.keySet()) {
					if(key.length() > longest.length()) longest = key;
					if(max == words.get(key)) most = key;
				}

				System.out.println(most + " " + longest);
			
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

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

int main(){
  int A,B;
  cin >> A >> B;
  if((A>=0)&&(A<=9)&&(B>=1)&&(B<=9)){
    cout << A*B << endl;
  }else{
    cout << -1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100004];
int main(){
	int n,k,q;cin>>n>>k>>q;
	for (int i=1;i<=q;i++){
		int x;cin>>x;a[x]++;
	}
	for (int i=1;i<=n;i++){
		if (k-(q-a[i])<=0){
			puts("No");continue;
		}
		puts("Yes");
	}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  string S;
  cin >> S;
  int memo = 0;
  int k = S.size();
  for (int i = 0; i < k; i++) {
    if (S.at(i) == '1') {
      memo++;
    }
  }
  cout << min(k - memo, memo) * 2 << endl;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const int N = 2505;
const int MAX_ITER = 2505;
const ll INF = 1e18;

int n, m;
ll p;
vector <pair <int, ll> > nb[N], rev_nb[N];
bool vis[N], in_path[N], connected[N];

void DFS_connected(int v)
{
    connected[v] = true;
    for(auto t: rev_nb[v])
        if(!connected[t.first])
            DFS_connected(t.first);
}

void DFS_check_infinite(int v)
{
    vis[v] = true;
    for(auto t: nb[v])
        if(!vis[t.first])
            DFS_check_infinite(t.first);
}

ll dp[N][MAX_ITER];
void solve(int time)
{
    for(int i = 1; i <= n; i++)
    {
        dp[i][time] = dp[i][time - 1];
        for(auto t: rev_nb[i])
            dp[i][time] = max(dp[i][time], dp[t.first][time - 1] + t.second);
    }
}

ll dist[N];
bool neg_cycle()
{
    dist[1] = 0;
    for(int i = 2; i <= n; i++)
        dist[i] = INF;
    for(int time = 1; time < n; time++)
    {
        for(int i = 1; i <= n; i++)
            for(auto t: rev_nb[i])
                dist[i] = min(dist[i], dist[t.first] - t.second);
    }

    for(int i = 1; i <= n; i++)
        for(auto t: rev_nb[i])
            if(dist[t.first] - t.second < dist[i] && connected[i] && vis[i])
                return true;

    return false;
}

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

    int u, v, c;

    cin >> n >> m >> p;
    for(int i = 1; i <= m; i++)
    {
        cin >> u >> v >> c;
        nb[u].pb({v, c - p});
        rev_nb[v].pb({u, c - p});
    }

    DFS_connected(n);
    DFS_check_infinite(1);
    if(neg_cycle())
    {
        cout << -1 << endl;
        return 0;
    }

    dp[1][0] = 0;
    for(int i = 2; i <= n; i++)
        dp[i][0] = -INF;

    ll ans = 0;
    for(int i = 1; i < n; i++)
    {
        solve(i);
        ans = max(ans, dp[n][i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 49792
from itertools import permutations

n, m, r = map(int, input().split())
city = list(map(int, input().split()))
for i in range(r):
    city[i] -= 1
to = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    to[a].append([b, c])
    to[b].append([a, c])

INF = 10**15
dist = [[INF for _ in range(n)] for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
    for j in range(len(to[i])):
        dist[i][to[i][j][0]] = to[i][j][1]
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

ans = INF
for v in permutations(city):
    tmp = 0
    for i in range(r-1):
        tmp += dist[v[i]][v[i+1]]
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 52056
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

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

  int A[N - 1];
  rep(i, N - 1) cin >> A[i];

  int count[N];
  rep(i, N) count[i] = 0;

  rep(i, N - 1) { count[A[i] - 1]++; }
  rep(i, N) cout << count[i] << endl;

  return 0;
}


Measured memory_bytes: 5168
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(2);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    while(cin>>n,n){
        vi p(n+1),t(n+1);
        REP(i,1,n)cin>>p[i]>>t[i];
        vvi dp(n+1,vi(4));
        rep(i,n+1)rep(j,4)dp[i][j]=40000;
        dp[0][0]=0;
        int bad=0;
        rep(i,n){
            rep(j,4){
                bool ok=false;
                if(dp[i][j]==40000)continue;
                int d=abs(p[i+1]-p[i]);
                int m=d*(j+1);
                if(j<3&&m<=t[i+1]-t[i]){
                    dp[i+1][j+1]=min(dp[i][j]+d,dp[i+1][j+1]);
                    ok=true;
                }
                if(p[i]*(j+1)+p[i+1]<=t[i+1]-t[i]){
                    dp[i+1][1]=min(dp[i][j]+p[i]+p[i+1],dp[i+1][1]);
                    ok=true;
                }
                if(!ok){
                    bad=max(bad,i+1);
                }
            }
        }
        int ans=40000;
        rep(i,4)ans=min(dp[n][i]+p[n],ans);
        if(ans>=40000){
            cout<<"NG "<<bad<<endl;
        }
        else {
            cout<<"OK "<<ans<<endl;
        }
    }
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    ll min_ = INF;
    min_ = min(a, min(b, min(c, min(d, e))));
    cout << (n - 1) / min_ + 5 << endl;
    return 0;
}

Measured memory_bytes: 3572
/*
    author: Salam_35
    Created at :

*/

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

#define ll long long int
#define pb push_back
#define sc(n) scanf("%d",&n)
#define Max 100005
#define scan(n) scanf("%lld",&n)
#define pi acos(-1.0)
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ALL(x) x.begin(),x.end()
#define sci(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define load(array,size)  for(ll i=0 ; i<size ; i++) cin>>array[i] ;
#define load1(array,size)  for(ll i=1 ; i<=size ; i++) cin>>array[i] ;
#define INF	1LL<<19
#define pll pair<ll,ll>
#define mst(arr,value) memset(arr,value,sizeof(arr));


const ll MOD = 1e9+7;

typedef vector<ll>vec;
typedef pair<ll,ll> pii;
typedef map<ll,ll>mpll;
typedef set<ll>seet;
vec primes;


int main()
{
    int h,n;
    cin >> h >> n;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        int a;
        cin >> a;
        sum+=a;
    }

    if(sum>=h)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
#define FI first
#define SE second
#define PB push_back
#define EB emplace_back
#define SZ(x) (int)(x).size()
#define BN(x) ((1<<x)-1)
#define DUP(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

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 () {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi b(n);
  rep(i,n) cin >> b[i];
  vi c(n-1);
  rep(i,n-1) cin >> c[i];
  rep(i,n) a[i]--;

  int ans = 0;
  rep(i,n) {
    ans += b[a[i]];
  }

  rep(i,n-1) {
    if (a[i]+1 == a[i+1]) {
      ans += c[a[i]];
    }
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 1000000000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>//usage rand<long long>()
T rand() {
    return uniform_int_distribution<T>()(rng);
}

// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

//////////////

#define S second
#define F first
#define int long long  

//////////

signed main()
{
	fastio;
	// #ifndef ONLINE_JUDGE
	// 	freopen("inputf.in","r",stdin);
	// 	freopen("outputf.in","w",stdout);
	// #endif
	int H,W;
	cin>>H>>W;
	int h,w;
	cin>>h>>w;
	cout<<H*W-(h*W+w*H-h*w);
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int n,b,f,r,v;
    scanf("%d",&n);
    int ninzu[4][3][10];
    for(int i=0;i<4;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<10;k++)
                ninzu[i][j][k]=0;
    for(int i=0;i<n;i++){     
        scanf("%d %d %d %d",&b,&f,&r,&v);
        ninzu[b-1][f-1][r-1]+=v;
    }    
    for(int i=0;i<4;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<10;k++){
                printf(" %d", ninzu[i][j][k]);
            }
            printf("\n");
        }
    if(i<3)  puts("####################");
    }
    return 0;
}                


Measured memory_bytes: 2104
//Tuvshee
 
#include<iomanip>
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<cmath>
#include<algorithm>
#include<string>
#include<cctype>
#include<vector>
#include<queue>
using namespace std;
#define I int
#define D double
#define F float
#define C char
#define S string
#define B bool
#define L long long
#define rep(n) for(int i=0;i<n;i++)
#define reps(m,n,c) for(int c=m;c<n;c++)
#define repd(m,n,j) for(int j=n;j>m;j--)
#define whL while
#define eL endl
#define oR ||
#define anD &&
#define rtn return
#define pause system("PAUSE")
#define Max 300
#define max(m,n) ((n<m)?m:n)
#define min(m,n) ((n>m)?m:n)
 
int main()
{
	L a,b;
	C op;
	for(;;){
		cin>>a>>op>>b;
		if(op=='?')rtn 0;
		else if(op=='+')cout<<a+b<<eL;
		else if(op=='-')cout<<a-b<<eL;
		else if(op=='*')cout<<a*b<<eL;
		else if(op=='/')cout<<a/b<<eL;
	}
	rtn 0;
}

Measured memory_bytes: 1156
a=[1e4]*51
for i,j in[(2,380),(3,550),(5,850),(10,1520),(12,1870),(15,2244)]:
 a[i]=j
 for k in range(51-i):
  if a[k+i]>a[k]+j:a[k+i]=a[k]+j
for n in iter(input,'0'):print(a[int(n)//100])


Measured memory_bytes: 5612
al = list(map(int,input().split()))

al = sorted(al)

a = al[2] - al[1]
b = al[2] - al[0]

k = min(a,b)

if (k - b) % 2 == 1:
    print(k + (b - k) // 2 + 2)
else:
    print(k + (b - k) // 2)

Measured memory_bytes: 38384
from collections import deque
n, m = map(int, input().split())
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
if Yes:
    s=sum(color)
    print(s*(n-s)-m)
else:
    print(n*(n-1)//2-m)

Measured memory_bytes: 26896
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [x, y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    #heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][1], xy[i][2]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Measured memory_bytes: 132200
import java.util.*;

public class Main {

    // global
    static long fact[];
    static long inverse[];
    static int mod = 998244353;

    static long pow(long a,int n) {
        long res=1;
        while (n>0) {
            if ((n-n/2*2)==1) {
                res=res*a%mod;
            }
            a=a*a%mod;
            n>>=1;
        }
        return res;
    }

    static long modinv(long n) {
        return pow(n, mod-2);
    }

    static long comb(int n,int k){
        if(n<0 || k<0 || n<k)return 0;
        return fact[n]*(inverse[k]*inverse[n-k]%mod) %mod;
    }

    public static void main(String[] args) {

        // main method
        fact=new long[500000];
        fact[0]=1;
        inverse=new long[500000];
        inverse[0]=1;
        for(int i=1;i<500000;i++){
            fact[i]=(fact[i-1]*(long)i)%mod;
            inverse[i]=modinv(fact[i]);
        }

        Scanner sc = new Scanner(System.in);
        long N = Long.parseLong(sc.next());
        long A = Long.parseLong(sc.next());
        long B = Long.parseLong(sc.next());
        long K = Long.parseLong(sc.next());

        // solve Ax+By=K
        long ans = 0L;
        for (int i=0;i<=N;i++) {
            if ((K-A*i)%B==0) {
                long j = (K-A*i)/B;
                if (0<=j && j<=N) {
                    ans = (ans + comb((int)N, i)*comb((int)N, (int)j)%mod)%mod;
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 31956
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() (int, error) {
	return strconv.Atoi(nextString())
}

func calc(m, f, r int) string {
	g := ""
	if m < 0 || f < 0 {
		g = "F"
	} else if m+f >= 80 {
		g = "A"
	} else if m+f >= 65 {
		g = "B"
	} else if m+f >= 50 {
		g = "C"
	} else if m+f >= 30 {
		if r >= 50 {
			g = "C"
		} else {
			g = "D"
		}
	} else {
		g = "F"
	}
	return g
}
func main() {
	scanner.Split(bufio.ScanWords)

	for {
		m, _ := nextInt()
		f, _ := nextInt()
		r, _ := nextInt()
		if m == -1 && f == -1 && r == -1 {
			break
		}
		fmt.Println(calc(m, f, r))
	}
}



Measured memory_bytes: 1060
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define all(a) begin(a),end(a)
#define sz(a) (int)(a.size())
#define deb(a) cout << #a << ": " << a << ENDL
#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;

lli INF = 1e18;

int main()
{   _
    lli n; cin >> n;
    vi v(n); fore(i, 0, n) cin >> v[i];
    vector<vector<lli>> dp(n, vector<lli>(n, INF));
    fore(i, 0, n) dp[0][i] = 0;
    vector<lli> acum(n + 1, 0);
    fore(i, 1, n + 1) acum[i] = acum[i - 1] + v[i - 1];
    fore(i, 1, n) {
        fore(j, 0, n - i) {
            lli range = acum[j + i  + 1] - acum[j];
            fore(k, 0, i) {
                dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k - 1][j + k + 1] + range);
            }
        }
    }
    cout << dp[n - 1][0] << ENDL;
    return 0;
}


Measured memory_bytes: 4508
# stdin
INPUT_SENTENCES = 2
ss = [input() for i in range(INPUT_SENTENCES)]
n = int(ss[0])
p = [int(i) for i in ss[1].split()]
result = 0
for i in range(1, n-1):
    if p[i-1] < p[i] < p[i+1] or p[i-1] > p[i] > p[i+1]:
      result += 1
print(result)
    


Measured memory_bytes: 3060
h,w=[int(j) for j in input().split()]
s=[input()for i in range(h)]
par=[-1 for i in range(h*w)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(h):
    for j in range(w):
        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
            p,q=i+x,j+y
            if 0<=p<h and 0<=q<w:
                if s[p][q]!=s[i][j]:
                    if root(w*p+q)!=root(w*i+j):
                        connect(w*p+q,w*i+j)

from collections import Counter
c=Counter()
for i in range(h):
    for j in range(w):
        p=i*w+j
        q=root(p)
        if c[q]==0:
            c[q]=[0,0]
        if s[i][j]=="#":
            c[q][0]+=1
        else:
            c[q][1]+=1
ans=0
for i in c:
    ans+=c[i][0]*c[i][1]
print(ans)


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int k, s;
    cin >> k >> s;
    ll ans = 0;
    rep(x, k+1) rep(y, k+1) {
        int z = s - x - y;
        if (z < 0 || z > k) continue;
        if (x + y + z == s) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#define numarr 12
using namespace std;

int main() {
	int a[5], k, i, amin = 200, amax = -1;
	for (i = 0; i < 5; i++)
	{
		cin >> a[i];
		amin = min(amin, a[i]);
		amax = max(amax, a[i]);
	}
	cin >> k;

	if (amax - amin <= k)
	{
		cout << "Yay!" << endl;
	}
	else cout << ":(" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
using namespace std;
int divisor[200];

int main(){
    for(int i=1;i<=200;i++){
        for(int j=i;j<=200;j+=i){
            divisor[j] = divisor[j]+1;
        }
    }

    int n,cnt=0;
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        if(divisor[i]>=8 && i%2==1) cnt++;

    printf("%d\n",cnt);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    long long p,i,j,l,m,n;
    cin>>p;
    long long a[p],b[p],c[p],d[p],e[p],inv[p];
    for(i=0;i<p;i++){
        cin>>a[i];
        c[i]=0;d[i]=0;e[i]=0;
    }
    for(i=0;i<p;i++){
        n=1;
        for(j=0;j<p-2;j++){
            n=(n*i)%p;
        }
        inv[i]=n;
    }
    for(i=0;i<p;i++){
        m=0;n=1;
        for(j=0;j<i;j++){
            m+=b[j]*n;
            m%=p;
            n=(n*(i-j))%p;
        }
        m=a[i]-m;
        n=1;
        for(j=0;j<i;j++){
            n=(n*(j+1))%p;
        }
        l=inv[n];
        b[i]=((m*l)%p+p)%p;
    }
    c[0]=1;
    for(i=0;i<p;i++){
        for(j=0;j<p;j++){
            e[j]=(e[j]+b[i]*c[j])%p;
        }
        d[0]=(c[0]*(-i))%p;
        for(j=1;j<p;j++){
            d[j]=(c[j]*(-i)+c[j-1])%p;
        }
        for(j=0;j<p;j++){
            c[j]=d[j];
        }
    }
    for(i=0;i<p;i++){
        e[i]=(e[i]+p)%p;
        cout<<e[i];
        if(i<p-1){
            cout<<" ";
        }
    }
    cout<<endl;
    for(i=0;i<p;i++){
        m=0;n=1;
        for(j=0;j<p;j++){
            m=(m+e[j]*n)%p;
            n=(n*i)%p;
        }
        if(a[i]!=m){
            cout<<i<<endl;
        }
    }
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <cctype>

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i,l,n) for(int (i)=(int)(l);(i)<(int)(n);(i)++)
#define d_arr(arr, h, w) rep(i,(h) ){ cout << "["; rep(j,(w) ) { cout << (arr)[i][j] << ", "; } cout << "]" << endl;}
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x);
#define fs first
#define sc second

typedef pair<int ,int> P;

char grid[20][20];
bool arrived[20][20];
int dx[4] ={1,0,-1,0};
int dy[4] ={0,1,0,-1};
int w,h;

//i,jから初めて到達可能なタイルの数の最大値(i,j)含む
void rec(int i,int j){
//    printf("i:%d j:%d\n",i,j);
    arrived[i][j] = true;
    grid[i][j] = '#';
    int ret = 0;
    rep(k,4) {
        int next_j = j+dx[k];
        int next_i = i+dy[k];
        if( next_j < w && 0 <= next_j &&
            next_i < h && 0 <= next_i &&
            grid[next_i][next_j] == '.')
        {
            rec(next_i,next_j);
        }
    }
}

int main()
{
    P start;
    while(1){
        cin >> w >> h;
        if( w==0 && h==0 ) {break;}
        rep(i,20) rep(j,20) arrived[i][j] = false;
        rep(i,h){
            rep(j,w){
                cin >> grid[i][j];
                if( grid[i][j] == '@' ){ start.first=i;start.second=j; }
            }
        }
        rec(start.first,start.second);
        int ret=0;
        rep(i,20){
            rep(j,20){
                if(arrived[i][j] == true ){
                    ret+=1;
                }
            }
        }
        cout << ret << endl;
    }
}

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

using namespace std;

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

    int N;
    cin >> N;
    int len = (1 << N);
    vector<int> S(len);
    multiset<int> todo;
    for (int i = 0; i < len; ++i) {
        cin >> S[i];
        todo.insert(S[i]);
    }
    vector<int> act;
    auto it = --end(todo);
    act.push_back(*it);
    todo.erase(it);

    for (int i = 0; i < N; ++i) {
        int m = act.size();
        for (int j = 0; j < m; ++j) {
            it = todo.lower_bound(act[j]);
            if (it == begin(todo)) {
                cout << "No\n";
                return 0;
            }
            --it;
            act.push_back(*it);
            todo.erase(it);
        }
        sort(begin(act), end(act));
        reverse(begin(act), end(act));
    }
    cout << "Yes\n";

    return 0;
}

Measured memory_bytes: 14712
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]

f, s = [],[]

for i in range(m):
    if l[i][0] == 1:
        f += [l[i][1]]
    if l[i][1] == n:
        s += [l[i][0]]

print('POSSIBLE') if set(f) & set(s) else print('IMPOSSIBLE')

Measured memory_bytes: 61020
#include <iostream>

int main() {
	int n, a[100];
	std::cin >> n;
	for (int i = 0; i < n; i++)
		std::cin >> a[i];
	for (int i = n - 1; i >= 0; i--)
		std::cout << a[i] << (i == 0 ? '\n' : ' ');
}


Measured memory_bytes: 3080
implicit none
integer(8):: n,y,i,j,count,s_len
character(10**5+5)::s,s_rev
character(5)::a
character(5)::b
character(6)::c
character(7)::d

a="maerd"
b="esare"
c="resare"
d="remaerd"

s_rev=""

read(5,*) s
s_len=len_trim(s)

do i=1,s_len
    s_rev(s_len+1-i:s_len+1-i)=s(i:i)
enddo

!write(6,*) trim(s_rev)

count=1

do while (count<=s_len)

!    write(6,*) index(s_rev,a),index(s_rev,b),index(s_rev,c),index(s_rev,d)
    
    if (index(s_rev,a)==1) then
        count=count+5
        s_rev=s_rev(6:) 
    else if (index(s_rev,b)==1) then
        count=count+5
        s_rev=s_rev(6:)         
    else if (index(s_rev,c)==1) then
        count=count+6
        s_rev=s_rev(7:)         
    else if (index(s_rev,d)==1) then
        count=count+7
        s_rev=s_rev(8:)         
    else 
        write(6,*) "NO"
        goto 100
        
    endif
    
!    write(6,*) trim(s_rev)
    
enddo

write(6,*) "YES"
 
100 end



Measured memory_bytes: 828
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

class CRemainderMinimization2019 {
public:
	void solve(std::istream& in, std::ostream& out) {
	    ll l,r;
	    in>>l>>r;
	    const ll mod=2019;
	    r=min(r,l+4038);
	    ll ans=INF;
	    for(ll i=l; i<=r; i++){
	        for(ll j=i+1; j<=r; j++){
	            ans=min(ans,i*j%mod);
	        }
	    }
	    out<<ans<<endl;


	}
};


int main() {
	CRemainderMinimization2019 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 888
A,B,C,X=[int(input()) for i in range(4)]
ans = 0
for i in range(A+1):
    for j in range(B+1):
        tmp = X-500*i-100*j
        if tmp < 0:
            break
        if tmp%50==0 and tmp//50<=C:
            ans += 1
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	for(int i=0;i<min(a.size(),b.size());i++){
	    cout<<a[i]<<b[i];
	}
	if(a.size()>b.size()){
	    for(int i=b.size();i<a.size();i++){
	        cout<<a[i];
	    }
	}
	else{
	    for(int i=a.size();i<b.size();i++){
	        cout<<b[i];
	    }
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };


signed main() {
	int n, m, maxn = 0;
	vector<int>list;

	cin >> n >> m;

	int oldsum = 0;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		list.push_back(num);
		oldsum += num;
	}

	vector<pair<int, int>>sousa;

	for (int i = 0; i < m; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		sousa.push_back(make_pair(-num2, num1));
	}

	sort(list.begin(), list.end());
	sort(sousa.begin(), sousa.end());

	int index = 0, cnt = 0, sum = 0;
	bool flag2 = false;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < sousa[i].second; j++) {
			cnt++;
			if (list[index] < abs(sousa[i].first)) {
				sum += (abs(sousa[i].first) - list[index]);
				//list[index] = sousa[i].first;
				index++;
				
			}
			else {
				break;
			}

			if (index == n - 1) {
				index = 0;
				sort(list.begin(), list.end());
			}

			if (cnt >= n) {
				flag2 = true;
				break;
			}
		}

		if (flag2 == true) break;
	}


	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < sousa[i].second; j++) {
	//		if (list[index] < sousa[i].first) {
	//			sum += (sousa[i].first - list[index]);
	//			list[index] = sousa[i].first;
	//			
	//			if (j != sousa[i].second - 1) {
	//				if (list[index + 1] < sousa[i].first) {
	//					index++;
	//				}
	//				else {
	//					index = 0;
	//					sort(list.begin(), list.end());
	//					break;
	//				}
	//			}
	//			else {
	//				index = 0;
	//				sort(list.begin(), list.end());
	//			}
	//		}

	//		/*if (index == n - 1) {
	//			index = 0;
	//			sort(list.begin(), list.end());
	//		}*/
	//	}
	//}

	cout << oldsum + sum << endl;





	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 3188
#include<iostream>
#include<atcoder/modint>
#include<atcoder/fenwicktree>
using namespace std;
using namespace atcoder;
using mint=modint998244353;
int N,K;
int P[2<<17];
main()
{
	cin>>N>>K;
	for(int i=0;i<N;i++)cin>>P[i];
	fenwick_tree<mint>A(N);
	fenwick_tree<int>B(N);
	mint ans=0;
	mint X=mint(K-1)/K;
	for(int j=1;j<N;j++)
	{
		A.add(P[j-1]-1,1/X.pow(max(j,K)-1));
		B.add(P[j-1]-1,1);
		ans+=(A.sum(0,P[j]-1)-A.sum(P[j],N))*X.pow(max(j,K-1))+2*B.sum(P[j],N);
	}
	cout<<(ans/2).val()<<endl;
}

Measured memory_bytes: 5636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
const int INF = 1000000001;

int N;
int H[100000];
bool checked[100000];

int main(){
  cin >> N;
  rep(i, N){
    cin >> H[i];
  }
  reverse(H, H+N);
  bool flag = true;;
  rep(i, N - 1){
    if(H[i] < H[i + 1]){
      if(H[i] + 1 < H[i + 1]){
        flag = false;
        break;
      }else{
        H[i+1]--;
      }
    }
  }
  if(flag){
    cout << "Yes" <<endl;
  }else{
    cout << "No" <<endl;
  }
}
  

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define H 100
#define W 100
char G[H][W];

int main() {
    i64 A, B; cin >> A >> B;
    A--; B--;
    REP(i, H / 2) {
        REP(j, W) {
            if (j % 2 == 0 && i % 2 == 0 && A > 0) {
                G[i][j] = '.';
                A--;
            } else {
                G[i][j] = '#';
            }
        }
    }

    for (i64 i = H / 2; i < H; i++) {
        REP(j, W) {
            if (i > (H / 2) && j % 2 == 0 && i % 2 == 1 && B > 0) {
                G[i][j] = '#';
                B--;
            } else {
                G[i][j] = '.';
            }
        }
    }

    cout << H << " " << W << endl;
    REP(i, H) {
        REP(j, W) cout << G[i][j];
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N, M = list(map(int, input().split()))

cities = {}
prefs = []

for i in range(1, M + 1):
  p, y = list(map(int, input().split()))
  
  pref = {"city": p, "year": y}
  prefs.append(pref)

  if p not in cities:
    cities[p] = [pref]
  else:
    cities[p].append(pref)

for city in cities.values():
  city.sort(key=lambda p: p['year'])
  for idx, pref in enumerate(city):
    pref['pref_id'] = str(idx + 1).zfill(6)

[print("%s%s" % (
  str(int(pref['city'])).zfill(6), 
  pref['pref_id'])) for pref in prefs]


Measured memory_bytes: 63516
#include <stdio.h>

int main(void)
{
    int i, j;

    for( i = 1; i <=9; i++ )
    {
        for( j = 1; j <=9; j++ )
        {
            printf("%dx%d=%d\n", i, j, i * j );
        }
    }

    return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

void helper(string s, int max_v, int N) {
    if (s.size() == N) {
        cout << s << endl;
        return;
    }
    for (int i=0; i<=max_v; i++) {
        helper(s + char('a' + i), max(max_v, i+1), N);
    }
}

int main() {
    int N; cin >> N;
    if (N == 1) {
        cout << "a" << endl;
        return 0;
    }
    helper("a", 1, N);
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int N,W;
ll dp[110][100100];
int main(){
    cin >> N >> W;
    vector<ll> w(N+1),v(N+1);
    rep1(i,N) cin >> w[i] >> v[i];
    
    rep1(i,N) rep(j,W+5){
        if(j >= w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        else dp[i][j] = dp[i-1][j];
    }
    
    pr(dp[N][W]);
}

Measured memory_bytes: 79488
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define  div "%lld"
#define  pdiv "%lld\n"
using namespace std;
///check n=1;
///check corner case;
map<ll,ll>check,str;

int main()
{
    FIO;
     string str;
     cin>>str;
     ll i,j=str.size();
     bool ok=true;
     for(i=0;i<j/2;i++){
         if(str[i] != str[j/2-1-i]){
            cout<<"No"<<endl;
            return 0;
         }
     }
     for(i=(j+3)/2;i<j;i++){
        if(str[i] != str[j-i-1]){
            cout<<"No"<<endl;
            return 0;
        }
     }
     cout<<"Yes"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>

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

int main() {
    int n;
    scanf("%d",&n);
    vector<int> a(n,0), b(n,0),c(n-1,0);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]); 
    for (int i = 0; i < n; i++) scanf("%d",&b[i]);
    for (int i = 0; i < n - 1; i++) scanf("%d",&c[i]);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += b[a[i]-1];
        if (i > 0 && a[i] == a[i-1] + 1) sum += c[a[i-1]-1];
    }
    printf("%d\n",sum);
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	s=RD()

	ans="NO"

	li=["KIHBR"
		,"AKIHBR","KIHABR","KIHBAR","KIHBRA"
		,"AKIHABR","AKIHBAR","AKIHBRA","KIHABAR","KIHABRA","KIHBARA"
		,"AKIHABAR","AKIHABRA","AKIHBARA","KIHABARA"
		,"AKIHABARA"]

	if s in li:
		ans="YES"

	print(ans)














if __name__ == "__main__":
	main()


Measured memory_bytes: 9064
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

from collections import defaultdict
def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    def check(k):
        D=defaultdict(lambda:-1)
        for i in range(n-k+1):
            h=rh[i:i+k]
            if(D[h]!=-1):
                if(i-D[h]>=k): return True
            else:
                D[h]=i
        return False

    print(bisection(0,n,check))
resolve()

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

typedef long long ll;

ll a[200005];

int main(void)
{
	ll n, mx = 0, sum = 0;

	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++)
		scanf("%lld", &a[i]);

	mx = a[1];

	for (ll i = 2; i <= n; i++)
	{
		if (mx < a[i])
			mx = a[i];

		sum += mx - a[i];
	}

	printf("%lld", sum);

	return 0;
}


Measured memory_bytes: 5336
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

const int aa[10]={0,2,5,5,4,5,6,3,7,6};
int n,m,ai;
vector<int> a,b;
string dp[10001];
bool cmp(string& s,string& t){
    if(s.size()!=t.size()) return s.size()>t.size();
    return s>t;
}
string dfs(int cur){
    if(cur==0) return "";
    else if(dp[cur].size()!=0&&dp[cur]!=" ") return dp[cur];
    string ret;
    rep(i,m)if(cur>=b[i]){
        string tmp;
        tmp+=('0'+a[i]);
        tmp+=dfs(cur-b[i]);
        if(tmp.back()!=' '&&cmp(tmp,ret)) ret=tmp;
    }
    if(ret.size()==0) ret=" ";
    return dp[cur]=ret;
}
int main(){
    cin>>n>>m;
    rep(i,m){
        cin>>ai;
        a.emplace_back(ai);
        b.emplace_back(aa[ai]);
    }
    string ans=dfs(n);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 27136
// C - Vacation
#include <bits/stdc++.h>
using namespace std;
// void abcprn(int a, int b, int c){printf("%4d,%4d,%4d\n",a,b,c);}

int main(){
	int N; cin>>N;
	int a,b,c; cin>>a>>b>>c;
	// cout<<"dp:a    b    c\n";//
	// abcprn(a,b,c);//
	while(--N){
		int pa=a, pb=b, pc=c;
		cin>>a>>b>>c;
		a += pb>pc? pb:pc;
		b += pc>pa? pc:pa;
		c += pa>pb? pa:pb;
		// abcprn(a,b,c);//
	}
	cout<< max({a, b, c}) <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = (int)(n)-1; 0 <= i; i--)
#define rrep1(i, n) for (int i = (int)(n); 1 <= i; i--)

#define each(it, c) \
    for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define all(obj) (obj).begin(), (obj).end()

#define pcount __builtin_popcount
#define SZ(x) ((int)(x).size())
#define LEN(x) ((int)(x).length())

#define dump(x) cerr << #x << " = " << (x) << endl;

#define endl "\n"

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;
}

typedef long long lint;

using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << (a + b < 24 ? a + b : a + b - 24) << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
int n, x, c[100], a[100];
int ans;
vector<int> s;
void dfs(int x) {
	if (x == 13) {
		int t = 24;
		for (int i = 0; i < s.size(); i++) {
			for (int j = 0; j < i; j++) {
				t = min(t, min(abs(s[i] - s[j]), 24 - abs(s[i] - s[j])));
			}
		}
		ans = max(ans, t);
	} else {
		if (c[x] == 0) {
			dfs(x + 1);
		} else if (c[x] == 1) {
			s.push_back(x);
			dfs(x + 1);
			s.pop_back();
			if (x != 0) {
				s.push_back(24 - x);
				dfs(x + 1);
				s.pop_back();
			}
		} else if (c[x] == 2) {
			s.push_back(x);
			if (x == 0) {
				s.push_back(x);
			} else {
				s.push_back(24 - x);
			}
			dfs(x + 1);
			s.pop_back();
			s.pop_back();
		}
	}
}
int main() {
	scanf("%d", &n);
	c[0]++;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (c[x] < 2) {
			c[x]++;
		} else {
			printf("0\n");
			return 0;
		}
	}
	dfs(0);
	printf("%d\n", ans);
}

Measured memory_bytes: 256