akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramB
    {
        static void Main()
        {
            int n = NextInt;
            var w = IntList;

            System.Console.WriteLine(Enumerable.Range(1, n - 1).Min(i => Math.Abs(w.Take(i).Sum() - w.Skip(i).Sum())));
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int len(ll x) {
  int l = 1;
  for (x /= 10; x > 0; x /= 10) l++;
  return l;
}
ll pow10(int p) {
  ll r = 1;
  REP(i,p)r*=10;
  return r;
}

int main() {
  ll n,k;
  while(cin>>n>>k,n||k) {
    ll cnt = 1;
    ll d = 9;
    int num = 0;
    int keta;
    for (keta=1; cnt+keta*d<n; ++keta) {
      cnt += keta*d;
      num += d;
      d*=10;
    }
    ll a = pow10(keta-1) + (n-cnt)/keta;
    int c = (n-cnt)%keta;
    stringstream ss;
    for (ll i=a; i<a+k+1; ++i) {
      ss << i;
    }
    string ans = ss.str();
    cout << ans.substr(c,k) << endl;
  }
}

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

using namespace std;

int main() {
  	long n, c = 0;
  	cin >> n;
	vector<long> l(n);
  	for ( int i = 0; i < n; i++ )
      	cin >> l[i];
  	sort( l.begin(), l.end() );
  	for ( int i = 0; i < n; ++i ) {
		for ( int j = 0; j < i; ++j ) {
			for ( int k = 0; k < j; ++k ) { 
              	if (  l[k] != l[j] && l[j] != l[i]  && l[k] + l[j] > l[i] )
                  			c++;
            }
        }
    }
  	cout << c << endl;
  	return 0;
}
    


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

long inf = 1000000007;


int main() {
	int a, b, k; cin >> k >> a >> b;

	for (int i = a; i < b + 1; i++) {
		if (i % k == 0) {
			cout << "OK" << endl;
			break;
		}
		

		if (i == b and i % k != 0) cout << "NG" << endl;
	}
}

	


Measured memory_bytes: 3636
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    int n = readint;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        auto ab = readints;
        int a = ab[0], b = ab[1];

        ans += b - a + 1;
    }
    writeln(ans);
}


Measured memory_bytes: 380
function MainA(input) {
	input = input.split("\n")[0].split(" ");
	var a = input[0];
	var b = input[1];
	var c = input[2];
	var result = (a == b && b == c) ? "Yes" : "No";

	console.log('%s',result);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
MainA(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
	Scanner in = new Scanner(System.in);

	int x,y;
	while(true){
	    x = in.nextInt();
	    y = in.nextInt();
	    if(x ==0 && y ==0)break;
	    if(x <= y)System.out.println(x + " " + y);
	    if(x > y)System.out.println(y + " " + x);
	    
	}
    }
}
	    



Measured memory_bytes: 36068
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define rev(v) reverse(v.begin(), v.end())
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define dab(v) for(auto i:v) cout << i << ' ' << endl;
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
#define vin2(v, w) for (ll i = 0; i < v.size(); ++i) cin >> v[i] >> w[i];
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; }
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }


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

	string S, T;
	cin >> S >> T;
	int cnt = 0;
	rep(i, S.size()){
		if(S.at(i)!=T.at(i)){
			cnt++;
		}
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3800
#include<bits/stdc++.h>
//#define int long long
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
#define endl '\n'
#define fori(s,n) for(int i=s;i<n;i++) 
#define forj(s,n) for(int j=s;j<n;j++) 
int OO = 1e9 + 9;
#define vii vector<int>
int n, k;
vii v;
int maxi = 1061109567;
int dp[100000 + 9];
int solve(int x) {

	if (x == n)
		return 0;
	if (x > n)
		return OO;
	int& ret = dp[x];
	if (ret != maxi) return ret;
	int r1 = abs(v[x] - v[x + 1]) + solve(x + 1);
	fori(2, k + 1)
		r1 = min(r1, abs(v[x] - v[x + i]) + solve(x + i));
	return ret = r1;
}
signed main()
{
	fast;
	memset(dp, '?', sizeof(dp));

	cin >> n >> k;
	v = vii(n + 101);
	fori(1, n + 1) cin >> v[i];
	cout << solve(1) << endl;
}


Measured memory_bytes: 11812
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++){
    cin >> h[i];
  }
  int count=1;
  int max = h[0];
  for(int j = 1; j < n; j++) {
    if(max <= h[j]){
      count++;
      max = h[j];
    }
  }
  cout << count;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define rn return
#define fi first
#define se second
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;


int main(){
    int r,D,x;
    cin >> r >> D >> x;
    rep(i,10){
        x = r*x - D;
        cout << x << endl;
    }
    
    rn 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:>
問題文============================================================

=================================================================

解説=============================================================

================================================================
*/
#define MAX_V 10010
struct edge{
    int to;
    int cap;
    int cost;
    int rev;
    edge(){}
    edge(int to,int cap,int cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
};

int V;
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost){
    G[from].push_back(edge(to,cap,cost,(int)G[to].size()));
    G[to].push_back(edge(from,0,-cost,(int)G[from].size()-1));
}

int min_cost_flow(int s,int t,int f){
    int res=0;
    while(f>0){
        fill(dist,dist+V,INF);
        dist[s]=0;
        bool update = true;
        while(update){
            update = false;
            for(int v=0; v<V ;v++){
                if(dist[v]==INF) continue;
                for(int i=0; i<G[v].size(); i++){
                    edge &e = G[v][i];
                    if(e.cap > 0 && dist[e.to] > dist[v]+e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }
        if(dist[t]==INF) return -1;
        
        int d = f;
        for(int v=t; v!=s; v=prevv[v])d=min(d,G[prevv[v]][preve[v]].cap);
        f -= d;
        res += d*dist[t];
        for(int v=t; v!=s; v=prevv[v]){
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}


int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    int M,N,K; cin >> M >> N >> K;

    V = K;
    
    int res = 0;
    vector<int> A(N);
    vector<vector<int> > B(N);
    for(int i = 0; i < N;i++) cin >> A[i];
    for(int i = 0; i < K;i++){
        int a; cin >> a; a--;
        B[a].push_back(i);
        res += A[a];
    }
    
    for(int i = 0; i < N;i++){
        if((int)B[i].size() <= 1) continue;
        for(int j = 0; j < (int)B[i].size()-1;j++){
            int s = B[i][j], t = B[i][j+1];
            if(s+1 != t){
                add_edge(s+1, t, 1, -A[i]);
            }else{
                res -= A[i];
            }
        }
    }
    for(int i = 0; i < K-1;i++){
        add_edge(i, i+1, M, 0);
    }
    cout << res + min_cost_flow(0, K-1, M-1) << endl;
	return 0;
}



Measured memory_bytes: 4496
#include <iostream>

using namespace std;
int i, n, x; bool ans=0;
int main()
{
    cin>>n;
    for(i=1; i<=n; ++i)
    {
        cin>>x;
        if(x&1) ans ^= 1;
    }

    if(ans) printf("NO\n");
    else printf("YES\n");

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
    int N,K; cin >> N >> K;
    vector<int> x(N);
    for(int i=0;i<N;i++){cin >> x[i];}
    int mi=1000000000;
    for(int i=0;i<=N-K;i++){
        int l=x[i],r=x[i+K-1];
        int xl = abs(l)+abs(r-l);
        int xr = abs(r)+abs(r-l);
        mi = min(mi,min(xl,xr));
    }
    cout << mi << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<ll> t(n);
  for(int i=0;i<n;i++) cin >> t[i];

  sort(t.begin(),t.end());

  ll lcm = t[0];
  for(int i=1;i<n;i++){
    lcm = t[i] / __gcd(t[i],lcm) * lcm;
  }

  cout << lcm << endl;
}


Measured memory_bytes: 256
from math import ceil

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

a = A1-B1
b = A2-B2

d = T1*a + T2*b

if d == 0:
    print('infinity')
    exit()
if a*b > 0 or a*d > 0:
    print(0)
    exit()

x = abs(T1*a)
d = abs(d)

cnt = (x+d-1)//d
if cnt*d == x:
    cnt = 2*cnt
else:
    cnt = 2*cnt-1

print(cnt)

Measured memory_bytes: 3064
#include<stdio.h>
int max(int a,int b){
  if(a>b) return a;
  else return b;
}
int main(void){
  int a,b,c,d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  printf("%d\n",max(a*b,c*d));
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
long long dis[100005];
long long vis[100005];
long long y[100005];
long long z[100005];
int main()
{
    long long C,N,form=0;
    long long you=0,temp=0,zuo=0,ymax=0,zmax=0;
    scanf("%lld %lld",&N,&C);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld %lld",&dis[i],&vis[i]);
        temp=vis[i]+temp-dis[i]+form;
        form=dis[i];
        if(ymax<temp-dis[i])
            ymax=temp-dis[i];
        y[i+1]=ymax;
    }
    y[1]=0;
    temp=0;
    form=C;
    for(int i=N;i>0;i--)
    {
        temp=vis[i]+temp-(form-dis[i]);
        form=dis[i];
        if(zmax<temp-(C-dis[i]))
            zmax=temp-(C-dis[i]);
            z[i-1]=zmax;
        if(zuo<temp+y[i])
            zuo=temp+y[i];
    }
    z[N]=0;
    temp=0;
    form=0;
    for(int i=1;i<=N;i++)
    {
        temp=vis[i]+temp-dis[i]+form;
        form=dis[i];
        if(you<temp+z[i])
            you=temp+z[i];
    }
    if(zuo>you)
        printf("%lld\n",zuo);
    else
        printf("%lld\n",you);
    return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 256;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
char s[MAXN];
bool vis[MAXN];
int main() {
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	if (len != 26) {
		for (int i = 1; i <= len; i++)
			vis[s[i]]++;
		for (int i = 'a'; i <= 'z'; i++)
			if (!vis[i]) {
				printf("%s%c\n", s + 1, i);
				return 0;
			}
	} else {
		for (int i = len; i >= 1; i--) {
			for (int j = s[i]; j <= 'z'; j++)
				if (vis[j]) {
					s[i] = j;
					printf("%s\n", s + 1);
					return 0;
				}
			vis[s[i]] = true, s[i] = 0;
		}
		puts("-1");
	}
	return 0;
}


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

using namespace std;

int main()
{
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int l = 0;
        int r = 0;
        int cnt = 0;
        bool ground = true;
        for (int i = 0; i < n; i++) {
            string str;
            cin >> str;
            if (str == "lu") {
                l++;
            } else if (str == "ru") {
                r++;
            } else if (str == "ld") {
                l--;
            } else {
                r--;
            }
            if (ground and r == 1 and l == 1) {
                cnt++;
                ground = false;
            } else if ((not ground) and r == 0 and l == 0) {
                cnt++;
                ground = true;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

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

int main(void) {
  int a, b, c, k;

  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &k);

  if((a > b && a > c)){
    a = a*pow(2, k);
  } else if (b > c){
    b = b*pow(2, k);
  } else {
    c = c*pow(2, k);
  }

  printf("%d", a+b+c);
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
int N,L[100];
main()
{
	cin>>N;
	for(int i=0;i<N;i++)cin>>L[i];
	int cnt=0;
	for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)for(int k=j+1;k<N;k++)
	{
		int A[3]={L[i],L[j],L[k]};
		sort(A,A+3);
		if(A[0]<A[1]&&A[1]<A[2]&&A[0]+A[1]>A[2])
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 string S;
 int count = 0;
 cin >> S;
 if(S.at(1) == 'R'){
   count = 1;
   if(S.at(0) == 'R') count++;
   if(S.at(2) == 'R') count++;
 }
 else{
   if(S.at(0) == 'R') count = 1;
   if(S.at(2) == 'R') count = 1;
 }
 cout << count;
  
}

Measured memory_bytes: 3620
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

vi divisors(int n) {
  vi v;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      v.pb(i);
      if (n != 1 && i * i != n) v.pb(n / i);
    }
  }
  sort(all(v));
  return v;
}

void solve() {
  int n;
  while (cin >> n, n) {
    vi v  = divisors(n);
    int s = accumulate(all(v), 0);
    s -= n;
    cout << (n > s ? "deficient" : n < s ? "abundant" : "perfect") << " number" << endl;
  }
}

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

int main()
{
    int n = 0;
    cin >> n;
    long m = 0;
    long a = 0;
    long r = 0;
    long c = 0;
    long h = 0;
    string s;
    for(int i = 0; i < n; i++){
        cin >> s;
        switch(s[0]){
            case 'M':
                m++;
                break;
            case 'A':
                a++;
                break;
            case 'R':
                r++;
                break;
            case 'C':
                c++;
                break;
            case 'H':
                h++;
                break;
        }
    }
    vector<long> v;
    v.push_back(m);
    v.push_back(a);
    v.push_back(r);
    v.push_back(c);
    v.push_back(h);
    sort(v.begin(), v.end());
    
    long long ans = 0;
    for(int i = 0; i < 3 ; i++){
        for(int j = i+1; j < 4; j++){
            for(int k = j+1; k < 5; k++){
                ans += v[i]*v[j]*v[k];
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

const int INF = 2e9;

int main() {
    int size_v, size_e;
    cin >> size_v >> size_e;
    int dist[110][110];
    for (int i = 0; i < size_v; i++) {
        for (int j = 0; j < size_v; j++) {
            dist[i][j] = INF;
        }
    }

    for (int i = 0; i < size_v; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < size_e; i++) {
        int s, t, d;
        cin >> s >> t >> d;
        dist[s][t] = d;
    }

    for (int k = 0; k < size_v; k++) {
        for (int i = 0; i < size_v; i++) {
            if (dist[i][k] == INF) {
                continue;
            }
            for (int j = 0; j < size_v; j++) {
                if (dist[k][j] == INF) {
                    continue;
                }
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    bool have_negacycle = false;
    for (int i = 0; i < size_v; i++) {
        if (dist[i][i] < 0) {
            have_negacycle = true;
        }
    }

    if (have_negacycle == true) {
        cout << "NEGATIVE CYCLE" << endl;
    }
    else {
        for (int i = 0; i < size_v; i++) {
            for (int j = 0; j < size_v; j++) {
                if (j != 0) {
                    cout << " ";
                }
                if (dist[i][j] == INF) {
                    cout << "INF";
                }
                else {
                    cout << dist[i][j];
                }
            }
            cout << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3168
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    K=int(input())
    S=input()
    if len(S)<=K:
        print(S)
    else:
        print(S[:K]+'...')

if __name__ == '__main__':
    main()


Measured memory_bytes: 61748
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>V(n);
  vector<int>C(n);
  
  for(int i = 0; i < n; ++i)
    cin >> V[i];
  for(int i = 0; i < n; ++i)
    cin >> C[i];
  int ans = 0;
  for(int i = 0; i < n; ++i)
  {
  	if(V[i] > C[i])
      ans += V[i] - C[i];
  }
  
  cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, K;
    int x[101];
    cin >> N >> K;
    int ans = 0;
    for(int i=0; i<N; ++i)
    {
        cin >> x[i];
        ans += min(K-x[i], x[i]);
    }
    cout << ans*2 << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Data;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        const long m = 1000000007;
        var n = long.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select(e => long.Parse(e) % m).ToArray();
        long sum = 0;
        var lis = new List<long>();
        for (int i = 0; i < n; i++)
        {
            sum = (sum + a[i]) % m;
        }
        var ans = 0L;
        for (int i = 0; i < n; i++)
        {
            sum -= a[i];
            if (sum < 0) sum += m;
            var ans2 = (a[i] * sum % m);
            ans = (ans + ans2) % m;
        }
        Console.WriteLine(ans);
    }
}


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

#include <math.h>
#define PI 3.14159265358979323846264338327950L



int main() {
    long long n, a, b;
    cin >> n >> a >> b;
    long long ans = 0;
    ans += (n / (a + b)) * a;
    if (n % (a + b) != 0) {
        ans += min((n % (a + b)),a);
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 3592
/*
 * Author : Sadi
 * Fri 03/07/2020
 * 23:09:31.01
 */
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    int s;
    cin >> s;
    vector<int> v;
    set<int> ms;
    ms.insert(s);
    v.push_back(s);
    while(1) {
        int value = 0;
        if(v.back() & 1) {
            value = 3 * v.back() + 1;
            v.push_back(value);
        }
        else {
            value = v.back() / 2;
            v.push_back(value);
        }
//        cout << value << endl;
        if(ms.find(value) != ms.end()) {
            cout << v.size() << endl;
            break;
        }
        else {
            ms.insert(value);
        }
    }

    return 0;
}


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


#define ALL(a) 		(a.begin() , a.end())
#define ll 			long long int
#define ff          first
#define ss          second
#define pb          push_back
#define ar 			array
#define mp 			make_pair
#define f(i,a,b)   	for(ll i =a;i<=b;i++)
#define inf 		INT_MAX
#define pll 		pair<ll,ll>
#define mat 		vector<vector<ll>>


#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 //debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }


 

const ll INF = 1e18;
void init(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE 
		freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
}
 
bool checkp2(ll n){
	return n && !(n & (n-1));
}

ll numsetbit(ll n){
	ll count = 0;
	for(;n;count++){
		n = n & (n-1);
	}
	return count;
}
 
ll powe(ll x , ll n ,const ll mod){
    x = x % mod;
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x) % mod;
		}
		n = n>>1;
		x = ((x % mod) * (x % mod)) % mod;
	}
	return po;
}

ll powm(ll x , ll n){
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x);
		}
		n = n>>1;
		x = (x*x);
	}
	return po;
} 



bool isPrime(ll x){
	if(x < 2)
		return 0;
	for(ll y = 2; y * y <= x; y++){
		if(x % y == 0){
			return 0;
		}
	}
	return true;
}
const ll  mod = 1e9 + 7;
void solve(){


	ll n;
	cin>>n;
	vector<ll> v1 , v2;

	for(ll i = 0;i<n;i++){
		ll x,y;
		cin>>x>>y;
		v1.pb(x+y);
		v2.pb(x-y);
	}
	sort(v1.begin() , v1.end());
	sort(v2.begin() , v2.end());

	cout<<max((v1.back() - v1[0]) , v2.back() - v2[0])<<endl;

	

		
}

int main(){
	
	//init();
	ll t = 1;
	//cin>>t;
	for(ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 6644
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;

    vector<string> table(h);
    for (auto& row : table)
    {
        cin >> row;
    }
    // vector<vector<int64_t>> dp(h, vector<int64_t>(w, 0));
    // dp[0][0] = 1;
    // for (int i = 1; i < h; i++)
    // {
    //     if (table[i][0] == '#')
    //     {
    //         dp[i][0] = dp[i - 1][0];
    //     }
    // }
    // for (int i = 1; i < w; i++)
    // {
    //     if (table[0][i] == '#')
    //     {
    //         dp[0][i] = dp[0][i - 1];
    //     }
    // }

    // for (int i = 1; i < h; i++)
    // {
    //     for (int j = 1; j < w; j++)
    //     {
    //         if (table[i][j] == '#')
    //         {
    //             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    //         }
    //     }
    // }

    int count = 0;
    for (auto& row : table)
    {
        for (auto& elem : row)
        {
            if (elem == '#')
            {
                count++;
            }
        }
    }

    cout << (count == (h + w - 1) ? "Possible" : "Impossible") << endl;
}


Measured memory_bytes: 256
N = int(input())
cards = list(map(int, input().split()))
cards.sort(reverse = True)#　.sort()　がポイント。.sort(reverse = True) で降順になる
Alice = 0
Bob = 0

for i in range(len(cards)):# range(len())　の記法はポイント
    if i % 2 == 0:
        Alice += cards[i]
    else:
        Bob += cards[i]

difference = Alice - Bob
print(difference)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
int main()
{
 	int n;
  	cin >> n;
  	vector<int> v(n);
  	for ( int i =0 ; i < n; i++ ){
     	cin >> v[i];
    }
  
  	int cnt =1 , ans =0;
  	for ( int i =0 ; i < n ; i ++ ){
      if ( v[i] == cnt ){
        ans++;
        cnt++;
      }
    }
  	cout << (ans ? n- ans : -1);
  
}

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

int main(){
    int H, W, n;
while(1){
    cin>>H>>W;
if(H==0 && W==0)break;
else
    for(int i=1;i<=H;i+=1){
        for(int j=1;j<=W;j+=1){
            if((i+j)%2==0)
              cout<<"#";
            else cout<<".";
           }
        cout<<endl;
       }
    cout<<endl;
}
    return 0;
}


Measured memory_bytes: 3068
//https://atcoder.jp/contests/abc150/tasks/abc150_c
//C - Count Order
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,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;}

template <class T>
struct fenwick_tree {
    int n;
    std::vector<T> x;
    fenwick_tree(int n_ = 0) : n(n_), x(n + 1, 0) {}
    int size() const { return n; }
    T sum(int r) const {
        T S = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
        return S;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int k, const T &a) {
        for (; k < n; k |= k + 1) x[k] += a;
    }
    void set(int k, const T &a) { add(k, a - sum(k, k + 1)); }
};

int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in");
    //std::ifstream in("./input.txt");
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif    
    ll N; cin>>N;
    vector<ll> pn(N);
    for(auto&& p:pn){ cin>>p; }
    vector<ll> qn(N);
    for(auto&& q:qn){ cin>>q; }

    vector<ll> fact(N+1);
    fact.at(1)=1;
    FOR(i,2,N+1){
        fact.at(i)=fact.at(i-1)*i;
    }

    auto lambda_count = [&](const auto& vec){
        ll result=0;
        fenwick_tree<ll> bit(N);
        FOR(i,0,vec.size()){
            ll va = vec.at(i);
            ll cnt=0;
            FOR(j,i+1,vec.size()){
                if(va>vec.at(j)) ++cnt;
            }
            result += (fact.at(N-i-1)*cnt);
            dump(N-i,cnt,result);
            bit.add(va,1);
        }
        return result;
    };

    ll a=lambda_count(pn);
    ll b=lambda_count(qn);
    ll ans=abs(a-b);
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int q = s.nextInt();
        
        int[] scores = new int[n];
        for (int i = 0; i < q; i ++) {
            int a = s.nextInt();
            scores [a - 1] ++;
        }
        
        for (int i = 0; i < n; i ++) {
            scores [i] += k - q;
            if (scores [i] > 0)
                System.out.println("Yes");
            else
                System.out.println("No");
        }
        
    }
    
}


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

int main()
{
	int a, b, c;
	int max, min, total = 0;
	scanf("%d %d %d", &a, &b, &c);
	total = a + b + c;
	if(a >= b && b >= c)
    {
		max = a;
    }   
	else if(b >= c && b >= a)
    {
    	max = b;
	}	
	else if (c >= a && c >= b)
	{
		max = c;
	}
	if(a <= b && b <= c)
    {
		min = a;
    }   
	else if(b <= c && b <= a)
    {
    	min = b;
	}	
	else if (c <= a && c <= b)
	{
		min = c;
	}
	printf("%d %d %d\n", min, total - max - min, max);
	return 0;
}


Measured memory_bytes: 2128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

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;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

vector<ll> now;

template <class T>
T sieve(T n){
	vector<bool> is_prime(n+1,true),prime(n+1);
	is_prime[0]=false;
	is_prime[1]=false;
	T ret=0;
	FOR(i,2,n+1){
		if(is_prime[i]){
			prime[ret++]=i;
			now.push_back(i);
			for(T j=2*i;j<=n;j+=i){
				is_prime[j]=false;
			}
		}
	}
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x;
	cin>>x;
	sieve(1e7);
	rep(i,now.size()){
		if(now[i]>=x){
			cout<<now[i]<<endl;
			return 0;
		}
	}
}

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

int main()
{
    int a[5] = {};
    int b[5] = {};
    int n;
    int x = 99;
    int j = 0;
    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        cin >> a[i];
        b[i] = a[i] % 10;
        if (b[i] != 0 && b[i] < x)
        {
            x = b[i];
            j = i;
                }
    }

    for (int i = 0; i < 5; i++)
    {
        if (i == j)
        {

            ans += a[i];
            //printf("%d\n", a[i]);
        }
        else
        {
            if (a[i] % 10 != 0)
            {
                n = (a[i] / 10 + 1) * 10;
                swap(a[i], n);
            }
            ans += a[i];
            //printf("%d\n", a[i]);
        }
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
    cin >> first;
    IN(rest...);
    return;
}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
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 vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second < b.second; }

const int MOD = 1000000007;

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

signed main() {
   SS(int,n,k);
   ll limit=n*(n-1)/2-(n-1);
   if(k>limit){
       p(-1);
       return 0;
   }else{
   vector<pair<int,int>>ans;
   rep(i,n-1)ans.push_back({i+1,n});//基本のうにを作る
   vector<pair<int,int>>edge;
   rep(i,n-1)rep(j,i)edge.push_back({i+1,j+1});//辺の候補を列挙
   
   rep(i,limit-k)ans.push_back(edge[i]);//求められた数まで貼る
   
   p(ans.size());
   rep(i,ans.size())cout<<ans[i].first<<" "<<ans[i].second<<endl;
   }
}

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

#define ll long long
#define INF 99999999
#define rep(i,n) for(int i=0,temp=(int)(n);i<temp;++i) 
#define repi(i,start,end) for(int i=start,temp=(int)(end);i<end;++i)
#define rfor(v,x) for(const auto& x : v) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n)
#define vsort(v) sort(v.begin(), v.end())
#define vfsort(v,lambda) sort(v.begin(),v.end(),lambda)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vin(v) rep(i,v.size()) {cin >> v[i];}
//最終奥義
#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//(lambda (x y) (< x y)) => [](int x, int y) -> int { return x<y; }


signed main(void){
  int l,r;cin >> l >> r;
  if(r-l>=2019){
    cout << 0 << endl;
    return 0;
  }
  repi(i,l,r+1){
    if(i%2019==0){
      cout << 0 << endl;
      return 0;
    }
  }


  l%=2019;r%=2019;
  int ans = 2019;
  repi(i,l,r)
    repi(j,i+1,r+1)
      chmin(ans,(i*j)%2019);
  cout << ans << endl;

  return 0;
}


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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int N;
set<int> S;
int main(){
  cin >> N;
  rep(i, N){
    int a;
    cin >> a;
    S.insert(a);
  }
  if(S.size() == N){
    cout <<"YES" <<endl;
  }else{
    cout << "NO" <<endl;
  }
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
#include <iomanip>
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
constexpr int MOD = 1000000007;

void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

int main ()
{
    int a,b;cin>>a>>b;
    int diff = b- a;
    int s = 0;
    REP(i,diff){
        s+= i;
    }
    cout<<s-a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const long long INF = 1e18;

int main(){
  int N;
  cin >> N;
  vector<long long> H(N), P(N);
  vector<pair<long long,int>> V;
  for(int i = 0; i < N; ++i){
    cin >> H[i] >> P[i];
    V.emplace_back(H[i]+P[i],i);
  }
  sort(V.begin(), V.end());
  vector<long long> DP(N+1,INF);
  DP[0] = 0;
  for(int i = 0; i < N; ++i){
    int idx = V[i].second;
    for(int j = N-1; j >= 0; --j){
      if(DP[j] == INF) continue;
      if(DP[j] > H[idx]) continue;
      DP[j+1] = min(DP[j+1],DP[j]+P[idx]);
    }
  }
  for(int i = N; i >= 0; --i){
    if(DP[i] < INF){
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 512
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n = ni()
t, a = na()
h = na()

ans = 0
c = inf
for i in range(n):
    p = t - h[i] * 0.006
    if abs(a - p) < c:
        c = abs(a - p)
        ans = i + 1

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int K,N;
    cin>>N>>K;
    int i,j;
    int a;
    ll sum=0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(i=0;i<N;i++){
        cin>>a;
        pq.push(a);
    }
    for(j=0;j<K;j++){
        a=pq.top();
        sum+=a;
        pq.pop();
    }
    cout<<sum<<endl;    
}

Measured memory_bytes: 3628
#include<iostream>
using namespace std;
int n,s,ans;
int solve(int c,int sum,int m){
  if(c==n && sum==s) ans++;
  for(int i=m;i<10;i++){
    solve(c+1,sum+i,i+1);
  }
}
int main(void){
  for(;;){
    cin >> n >> s;
    if(!n && !s) break;
    ans=0;
    solve(0,0,0);
    cout << ans << endl;
  }
}


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

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}
double cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
	return real(conj(a)*b);
}

struct L : public vector<P> {
	L() {}
	L(const P &a, const P &b) {
		push_back(a); push_back(b);
	}
};

typedef vector<P> G;

int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

// assumption : 3 <= ps.size()
G convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	G ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) // upper-hull
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}

bool intersectSP(const L &s, const P &p) {
	return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}

bool intersectSS(const L &s, const L &t) {
	return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
		ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}

#define curr(PP, i) PP[i]
#define next(PP, i) PP[(i+1)%PP.size()]
enum { OUT, ON, IN };
int contains(const G& g, const P& p) {
	bool in = false;
	for (int i = 0; i < g.size(); ++i) {
		P a = curr(g, i) - p, b = next(g, i) - p;
		if (imag(a) > imag(b)) swap(a, b);
		if (imag(a) <= 0 && 0 < imag(b))
			if (cross(a, b) < 0) in = !in;
		if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
	}
	return in ? IN : OUT;
}

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

	int N, M;
	while (cin >> N >> M)
	{
		if (N == 0) return 0;

		vector<P> BP(N);
		rep(i, 0, N)
		{
			double x, y;
			cin >> x >> y;
			BP[i] = P(x, y);
		}

		vector<P> WP(M);
		rep(i, 0, M)
		{
			double x, y;
			cin >> x >> y;
			WP[i] = P(x, y);
		}

		if (N == 1 && M == 1)
		{
			cout << "YES" << endl;
			continue;
		}
		else if (N == 2 && M == 1)
		{
			if (intersectSP(L(BP[0], BP[1]), WP[0]))
				cout << "NO" << endl;
			else
				cout << "YES" << endl;
		}
		else if (N == 1 && M == 2)
		{
			if (intersectSP(L(WP[0], WP[1]), BP[0]))
				cout << "NO" << endl;
			else
				cout << "YES" << endl;
		}
		else if (N == 2 && M == 2)
		{
			if (intersectSS(L(BP[0], BP[1]), L(WP[0], WP[1])))
				cout << "NO" << endl;
			else
				cout << "YES" << endl;
		}
		else
		{
			bool ok = true;
			if (3 <= N)
			{
				G B = convex_hull(BP);
				rep(i, 0, M)
				{
					if (contains(B, WP[i]) != OUT) ok = false;
				}
			}

			if (3 <= M)
			{
				G W = convex_hull(WP);
				rep(i, 0, N)
				{
					if (contains(W, BP[i]) != OUT) ok = false;
				}
			}

			if (ok)
				cout << "YES" << endl;
			else
				cout << "NO" << endl;
		}
	}
}

Measured memory_bytes: 3168