akhauriyash/Code-Regression huggingface dataset:
def main():
     n,k=map(int,input().split())
     if n*(n-1)//2-k<n-1:
          print(-1)
     else:
          cnt=0
          lim=int(n*(n-1)/2-k)
          print(lim)
          for i in range(1,n):
               if cnt==lim:
                    break
               for j in range(i+1,n+1):
                    print(i,j)
                    cnt+=1
                    if cnt==lim:
                         break
     
if __name__=='__main__':
     main()

Measured memory_bytes: 42736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


ll mod = 998244353;
ll dp[301][100010];
ll dp2[301][100010];

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

    ll n;
    cin>>n;
    ll a[n],sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum += a[i];
    }
    dp[0][0]=1;
    dp2[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=sum;j>=0;j--){
            dp[i+1][j] += dp[i][j]*2;
            dp[i+1][j] %= mod;
            dp[i+1][j+a[i]] += dp[i][j];
            dp[i+1][j+a[i]] %= mod;

            dp2[i+1][j] += dp2[i][j];
            dp2[i+1][j]%=mod;
            dp2[i+1][j+a[i]] += dp2[i][j];
            dp2[i+1][j]%=mod;
        }
    }
    ll ans = 1;
    for(int i=0;i<n;i++){
        ans = (ans*3)%mod;
    }
    for(int i=(sum+1)/2;i<=sum;i++){
        ans += mod - dp[n][i]*3;
        ans %= mod;
    }
    if(sum%2==0){
        ans += dp2[n][sum/2]*3;
        cerr << dp2[n][sum/2] << endl;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 469632
n,u,v=[int(j) for j in input().split()]
u,v=u-1,v-1
l=[[] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)
k=[10**18 for i in range(n)]
from collections import deque
q=deque([u])
k[u]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k[i]=k[p]+1

k2=[10**18 for i in range(n)]
from collections import deque
q=deque([v])
k2[v]=0
s=set()
while q:
    p=q.popleft()
    s.add(p)
    for i in l[p]:
        if i not in s:
            q.append(i)
            k2[i]=k2[p]+1
ll=[]
ans=0
for i in range(n):
    if k[i]<=k2[i]:
        ll.append(i)
        ans=max(ans,k2[i])


print(ans-1)

Measured memory_bytes: 85280
#include <stdio.h>

int x[105];

int main(){

	int N,K;

	scanf("%d",&N);
	scanf("%d",&K);

	int i;

	for(i=0;i<N;i++){
	scanf(" %d",&x[i]);
	}

	int ans=0;

	for(i=0;i<N;i++){
		if(x[i]>K-x[i]){
		ans+=2*(K-x[i]);
		}
		else{
		ans+=2*(x[i]);
		}
	}

	printf("%d\n",ans);

return 0;
}

Measured memory_bytes: 128
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>

#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

constexpr int inf = 2147483647;
constexpr int64_t inf64 = 9223372036854775807;
constexpr int mod = 1e9+7;

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

  int n;
  cin >> n;
  vector<Bint> arr(n);
  rep(i,n) cin >> arr[i];
  sort(arr.begin(), arr.end());

  Bint res = 1;
  rep(i,n) {
    res *= arr[i];
    if(res > 1000000000000000000) { cout << -1 << endl; return 0; }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 6508
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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

const long long INF = 1LL << 60;

int main(){
  int n, x; cin >> n >> x;
  vector<int> a(n+1);
  a[0] = 0;
  REP(i, 1, n) cin >> a[i];

  ll sum = 0;
  REP(i, 1, n){
    if(a[i-1] + a[i] > x){
      int cnt = a[i-1] + a[i] - x;
      a[i] -= cnt;
      sum += cnt;
    }
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 640
s = list(input())
ans = [1]*(len(s))
for i in range(len(s)-2):
    if s[i] == s[i+1] == 'R':
        ans[i+2] += ans[i]
        ans[i] = 0
for i in range(len(s)-1, -1, -1):
    if s[i] == s[i-1] == 'L':
        ans[i-2] += ans[i]
        ans[i] = 0
print(' '.join(map(str, ans)))

Measured memory_bytes: 11180
def f(x, A, F):
    result = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            result += A[i] - t
    return result


N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

lo = 0
hi = A[-1] * F[0]
while lo < hi:
    mid = (lo+hi)//2
    if K - f(mid, A, F) < 0:
        lo = mid+1
    else:
        hi = mid
print(lo)


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

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

  ll ans;
  if (M / 2LL <= N) {
    ans = M / 2LL;
  } else {
    ll rem = M - 2LL * N;
    ans = N + rem / 4LL;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis1=[];lis2=[]
for i in range(n):
    a,b=MI()
    lis1.append(a)
    lis2.append(b)
lis1.sort()
lis2.sort()
if n%2==1:
    ans=max(0,lis2[(n-1)//2]-lis1[(n-1)//2]+1)
else:
    sup1=lis2[n//2-1]
    sup2=lis2[n//2]
    low1=lis1[n//2-1]
    low2=lis1[n//2]
    ans=(sup1+sup2-low1-low2+1)
    ans=max(ans,0)
print(ans)

Measured memory_bytes: 25760
N = int(input())
A = list(map(int,input().split()))
A = [0] + A + [0]
wa = 0
rem1=[]
rem2=[]
add=[]

for i in range(1,len(A)):
    wa = wa + abs(A[i-1] - A[i])
    rem1.append(abs(A[i-1]-A[i]))
    rem2.append(abs(A[i]- A[i+1]) if i+1 < len(A) else 0)
    add.append(abs(A[i-1]-A[i+1]) if i+1 < len(A) else abs(A[i-1]))

for j in range(0,len(A)-2):
    print(wa-rem1[j]-rem2[j]+add[j])


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

vector <int> dp[100010], ed[100010];

int solve(int i, int j){
	
	if(j == (int)ed[i].size()) return 0;
	
	if(dp[i][j] == -1) dp[i][j] = max(solve(ed[i][j], 0) + 1, solve(i, j + 1));
	
	return dp[i][j];
}
	

int main(){
	
	int n, m, ans = 0;
	scanf("%d %d", &n, &m);
	
	for(int i = 0; i < m; i++){
		int a, b;
		scanf(" %d %d", &a, &b);
		
		ed[a].push_back(b);
		dp[a].push_back(-1);
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (int)ed[i].size(); j++){
			if(dp[i][j] == -1) solve(i, j);
			
			ans = max(dp[i][j], ans);
		}
	}
	
	printf("%d\n", ans);	
	
	return 0;
}


Measured memory_bytes: 16656
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, i321) => {
        read_value!($next, i32) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

//
// # Examples
//
// # integers
// input! { n: i32, m: i32, ... }
//
// # array
// input! { n: i32, v: [i32; n], }
//
// # matrix
// input! { n: i32, m: i32, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: i32,
//     w: i32,
//     board: [chars; h],
// }

// https://practice.contest.atcoder.jp/tasks/practice_1
//fn main() {
//    input!{
//        a: i32, b: i32, c: i32,
//        foo: chars,
//    }
//    let s: String = foo.into_iter().collect();
//    println!("{} {}", a+b+c, s);
//}
fn main() {
    input!{
        s: chars
    }
    let mut ans = 700;
    for i in 0..3 {
        if s[i] == 'o' {
            ans += 100;
        }
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;
typedef pair<int,int> P;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int h,w;
vector<string> s;
bool inf(int y,int x){
	return (y>=0&&y<h&&x>=0&&x<w)?true:false;
}
int bfs(int sy,int sx){
	int ret=0;
	queue<P> que;
	que.push(P(sy,sx));
	vector<vector<bool> > used(h,vector<bool>(w,false));
	while(!que.empty()){
		P t=que.front();
		que.pop();
		int y=t.first,x=t.second;
		if(used[y][x]){
			continue;
		}
		used[y][x]=true;
		ret++;
		for(int i=0;i<4;i++){
			int ny=dy[i]+y,nx=dx[i]+x;
			if(inf(ny,nx)&&!used[ny][nx]&&s[ny][nx]!='#'){
				que.push(P(ny,nx));
			}
		}
	}
	return ret;
}
int main(){
	
	
	while(cin>>w>>h,h||w){
		s=vector<string>(h);
		for(int i=0;i<h;i++){
			cin>>s[i];
		}
		int ans=0;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(s[i][j]=='@'){
					ans=bfs(i,j);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

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

#include <fstream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

#define gap                        ' '
#define EPS                        1e-9
#define P_INF                      2e9+17
#define N_INF                     -2e9-17
#define MOD                        1000000007
#define PI                         2*acos(0.0)
#define All(x)                     x.begin(),x.end()
#define Mem(Name, type)            memset(Name, type, sizeof(Name))

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

template<typename T>
T LCM(T a, T b) { return (a * b) / GCD(a, b); }

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto ob : v) os << ob << " ";
    return os;
}

template<typename T, typename S>
std::ostream &operator<<(std::ostream &os, const std::map<T, S> &v) {
    for (auto ob : v) os << ob.first << " : " << ob.second << std::endl;
    return os;
}

using ld = double;
using ll = long long int;
using ul = unsigned long long int;
using namespace std;

class CSumOfProductOfPairs {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        vector<ll> a(n), sum(n);
        for (int i = 0; i < n; ++i) {
            in >> a[i];
        }
        ll s = 0;
        for (int i = n - 1; i >= 0; --i) {
            s += a[i];
            sum[i] = s;
        }
        ll ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            ans += ((a[i] % MOD) * (sum[i + 1] % MOD)) % MOD;
        }
        out << ans % MOD << endl;
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    CSumOfProductOfPairs solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 6348
from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")


Measured memory_bytes: 48364
import random
import time

# 処理前の時刻
t1 = time.time() 

def f_last(d, i, lt):
  idx = []
  if i in lt[0:d]:
    idx = [j+1 for j, x in enumerate(lt[0:d]) if x == i]
  else:
    idx.append(0)
  return idx[-1]

d = int(input())
lc = list(map(int, input().split()))
ls = []
for _ in range(d):
  ls.append(list(map(int, input().split())))

v_max = -(10**5)
lt_max = [1]*d
while 1:
  lt = [random.randint(1, len(lc)) for i in range(d)]
  v = 0
  for dd in range(1, d+1):
    v_d = 0
    for i in range(len(lc)):
      v_d += lc[i]*(dd-f_last(dd, i+1, lt))
    v = v + ls[dd-1][lt[dd-1]-1] - v_d
  if v_max < v:
    v_max = v
    lt_max = lt[:]
  t2 = time.time()
  if t2-t1 > 1.8:
    break

for t in lt_max:
  print(t)

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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int expo(int base,int exponent,int mod){
    int ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
int n,q,a[3003],x[3003],y[3003];
int dp[3003][3003];
int f[3003][3003];
int inv2=(hell+1)/2;
void solve(){
    cin>>n>>q;
    rep(i,1,n+1){
        cin>>a[i];
    }
    rep(i,0,q){
        cin>>x[i]>>y[i];
    }
    rep(i,1,n+1){
        rep(j,1,n+1){
            dp[i][j]=i>j;
        }
    }
    for(int i=q-1;i>=0;i--){
        int l=x[i],r=y[i];
        rep(j,1,n+1){
            if(j==r) continue;
            f[l][j]=(dp[r][j]+dp[l][j])*inv2%hell;
        }
        rep(j,1,n+1){
            if(j==r) continue;
            f[j][l]=(dp[j][r]+dp[j][l])*inv2%hell;
        }
        rep(j,1,n+1){
            if(j==l) continue;
            f[r][j]=(dp[r][j]+dp[l][j])*inv2%hell;
        }
        rep(j,1,n+1){
            if(j==l) continue;
            f[j][r]=(dp[j][r]+dp[j][l])*inv2%hell;
        }
        f[l][r]=(dp[l][r]+dp[r][l])*inv2%hell;
        f[r][l]=(dp[l][r]+dp[r][l])*inv2%hell;
        rep(j,1,n+1){
            dp[j][l]=f[j][l];
            dp[j][r]=f[j][r];
            dp[l][j]=f[l][j];
            dp[r][j]=f[r][j];
        }
    }
    int ans=0;
    rep(i,1,n+1){
        rep(j,1,n+1){
            if(a[i]>a[j]) ans=(ans+dp[j][i])%hell;
        }
    }
    cout<<ans*expo(2,q,hell)%hell<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 141184
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int n, k; cin >> n >> k;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(RALL(l));
    int sum = 0;
    rep(i,k) sum += l[i];
    cout << sum << endl;
}

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

int main(){
    string S; cin>>S;
    int size=S.size();
    long long int ans=0,num=0;
    for(int i=0;i<(1<<size-1);i++){
        for(int j=0;j<size;j++){
            num=num*10+S[j]-'0';
            if(i&1<<j){
                ans=ans+num;
                num=0;
            }
        }
        ans=ans+num;
        num=0;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
Scanf.scanf "%d %d" (fun n m ->
    let mm = 1_000_000_007 in
    let ( +@) a b = (((a + b) mod mm) + mm) mod mm in
    let ( *@) a b = (a * b) mod mm in
    let calc lim =
        Scanf.scanf " %d" (fun offset ->
            let rec loop i coeff acc =
                if i = lim then acc else
                    let acc = acc +@ coeff *@ Scanf.scanf " %d" (fun x -> x - offset) in
                    loop (i + 1) (coeff + 2) acc
            in
            loop 1 (3 - lim) 0
        )
    in
    Printf.printf "%d\n" @@ (calc m *@ calc n)
)

Measured memory_bytes: 4608
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define ABS(x) ( (x)>0 ? x : -(x) )
#define MIN(x,y) ( (x) < (y) ? (x) : (y) )
#define MAX(x,y) ( (x) > (y) ? (x) : (y) )

#define INF 1000000000

void swap(int* x, int *y)
{
	int t;

	t = *x;
	*x = *y;
	*y = t;
}

int binary_search(int p[], int n, int key)
{
	int left, right, middle;

	left = 0;
	right = n-1;


	while (left <= right)
	{
		middle = (left + right) / 2;

		if (p[middle] == key)
			return middle;
		else if (p[middle] > key)
		{
			right = middle - 1;
		}
		else if (p[middle] < key)
		{
			left = middle + 1;
		}
	}

	return -1;

}

void bubble_sort(int p[], int n)
{
	int i, j;

	for (i = 0; i < n-1; i++)
	{
		for (j = 0; j < n - i - 1; j++)
		{
			if (p[j] > p[j + 1])
				swap(&p[i], &p[i + 1]);
		}
	}
}

int main()
{
	int a, b;

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

	printf("%d %d %f", a / b, a % b, (double)a / b);
}


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

//関数名：mod_pow
//概要：modつき指数関数
//第一引数a：指数の底
//第二引数b：指数
//第三引数mod：法となる値
//戻り値：a^b(m mod)
long long mod_pow(long long a, long long b, long long mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        long long d = mod_pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*mod_pow(a,b-1,mod)%mod;
}

//関数名：mod_combination
//概要：modつき二項係数
//第一引数n：組み合わせの全体
//第二引数r：何個取り出すか
//第三引数mod：法となる値
//戻り値：nCr(m mod)
//計算量O(nlog(mod))
long long mod_combination(long long n,long long r,long long mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; i--) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; i--) fact2 = fact2*i%mod;
    return fact1*mod_pow(fact2,mod-2,mod)%mod;
}


int main(){
    ll n,m; cin >> n >> m;
    ll k; cin >> k;
    ll ans = 0;
    ll comb = mod_combination(n*m-2,k-2,MOD);
    for(ll d = 1; d < n; d++){
        ans += d*(n-d)*m%MOD*m%MOD*comb%MOD;
        ans %= MOD;
    }
    for(ll d = 1; d < m; d++){
        ans += d*(m-d)*n%MOD*n%MOD*comb%MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
object Main extends App {
  val scanner = new java.util.Scanner(System.in)
  val n = scanner.nextInt()
  val m = scanner.nextInt()

  val anm = (1 to n).map { _ =>
    (1 to m).map(_ => scanner.nextInt())
  }

  val bm = (1 to m).map(_ => scanner.nextInt())

  val cm = anm.map { am =>
    (am zip bm).map {
      case (a, b) => a * b
    }.sum
  }

  cm.foreach(println)
}

Measured memory_bytes: 59368
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
const int ININF = 1000000;
int d[510][510];
int c[510][510];
int main() {
    int N, C;
    cin >> N >> C;
    rep(i, 0, C) {
        rep(j, 0, C) { cin >> d[i][j]; }
    }
    rep(i, 0, N) {
        rep(j, 0, N) {
            cin >> c[i][j];
            c[i][j]--;
        }
    }
    vector<vector<int>> v(3, vector<int>(C, 0));
    rep(cc, 0, C) {
        rep(i, 0, N) {
            rep(j, 0, N) { v[(i + j) % 3][cc] += d[c[i][j]][cc]; }
        }
    }
    long long min = INF;

    rep(i, 0, C) {
        rep(j, 0, C) {
            if(i == j)
                continue;
            rep(k, 0, C) {
                if(i == k || j == k)
                    continue;
                int sum = v[0][i] + v[1][j] + v[2][k];
                if(sum < min) {
                    min = sum;
                }
            }
        }
    }
    cout << min << endl;
}


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

int main(){
    string s;
    cin >> s;
    if(s=="AAA"||s=="BBB"){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 3592
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n-1):
    if (p[i] > p[i-1] and p[i] < p[i+1]) or (p[i] < p[i-1] and p[i] > p[i+1]):
        ans += 1
print(ans)


Measured memory_bytes: 3060
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($A,$B) =  explode(" ",trim(fgets(STDIN)));

$res = 0;
if ($A > $B) {
  $res+=$A;
  $A--;
}
else {
  $res+=$B;
  $B--;
}
if ($A > $B) {
  $res+=$A;
  $A--;
}
else {
  $res+=$B;
  $B--;
}
printf("%d\n",$res);


Measured memory_bytes: 4856
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
    int time;
    cin >> time;
    int h = time/3600;
    int m = time%3600/60;
    int s = time%60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 3212
alphabet = [0 for i in range(26)]

while True:
    try:
        word = input()
    except:
        break
    word_s=str.lower(word)
    for i in range(len(word_s)):
        a = ord(word_s[i])-ord('a')
        if (a >= 0 and a < 26):
            alphabet[a]+=1
        
for i in range(26):
    print(chr(i+ord('a')),":",alphabet[i])


Measured memory_bytes: 5568
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  ll N, K;
  while (cin >> N >> K) {
    ll T = N % K;
    ll res = min(T, abs(T - K));
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import sys
import collections
import copy


scan = sys.stdin.readline


def main():
    n, k = map(int, scan().rstrip().split())
    values = collections.deque([int(value) for value in scan().rstrip().split()])

    results = []

    for a in range(min(n, k) + 1):
        for b in range(min(n, k) - a + 1):
            hands = [0] * n
            v = copy.deepcopy(values)

            for _ in range(a):
                hands.append(v.popleft())
            for _ in range(b):
                hands.append(v.pop())

            hands.sort()

            c_d = 0
            for c_d in range(k - a - b):
                if hands[c_d] < 0:
                    hands[c_d] = 0
                else:
                    break
            results.append(sum(hands))
            hands = [0] * n

    results.sort(reverse=True)
    print(results[0])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
int n;
LL ans[90];
/**********************************************/

int main(){
    cin >> n;
    
    ans[0] = 2;
    ans[1] = 1;
    FOR(i, 2, n+1){
        ans[i] = ans[i-1]+ans[i-2];
    }    

    cout << ans[n] << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <bitset>
#include <math.h>
#define inp(X) cin >> X
#define out(X) cout << X << endl
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define SORT(A) sort(A.begin(),A.end())
using namespace std;

typedef long long int ll;
const ll MOD = 1e9+7;
#define INF 10000000000000


inline ll Upstair(ll n){
	ll rt;
	if(n==1) return 1;
	return n*Upstair(n-1);
}

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

class Tree
{
	public:
//		Tree(int _root);
		int root;
		vector<int> next;
		int value = 0;
};

template<class T>
class Vec3
{
	public:
		T act[3];
};

int Stair( int now, vector<ll> &H )
{
	if( H[now] >= H[now+1] ){}
	
}

int main(void) {
	
	ll N,W;
	inp(N);
	inp(W);
	vector<ll> weight(N);
	vector<ll> value(N);
	rep(i,N){
		inp(weight[i]);
		inp(value[i]);
	}
	vector<vector<ll>> dp_v(N+1, vector<ll>(W+1));
	rep(w,W+1) dp_v[0][w] = 0;
	
	rep(i,N)rep(w,W+1){// i:品物番号 w:ナップサックの重さ
		if( weight[i] <= w ){//まだ入るなら
			dp_v[i+1][w] = max(dp_v[i][w],//入れない
							 dp_v[i][w-weight[i]]+value[i]//入れる
							);
		}else{//入らないなら
			dp_v[i+1][w] = dp_v[i][w];//入れない
		}
	}
/*	
	rep(i,N+1){
		rep(w,W+1){
			cout << dp_v[i][w] << " , ";
		}
		cout << endl;
	}
*/
	ll ans = dp_v[N][W];
	out(ans);
	
		
}

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

//ABC063C

const int N = 105;
const int S = 105;
int n, s;
bool can[N*S];

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

	fill(can, can + N*S, false);

	cin >> n;

	can[0] = true;


	for(int i = 0; i < n; i++) {
		cin >> s;
		for(int j = N*S-1; j >= s; j--) {
			if(can[j-s]) can[j] = true;
		} 
	}

	int maxi = 0;
	for(int i = 0; i < N*S; i++) {
		if(can[i] && (i%10 != 0)) maxi = i;
	}

	cout << maxi << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

arr = [i_i() for _ in range(5)]
arr.sort(key=lambda a: a%10)

flag = True
ans = 0
for x in arr:
    if flag and x % 10 >= 1:
        ans += x
        flag = False
    else:
        if x % 10 != 0:
            ans += (x + 10) // 10 * 10
        else:
            ans += x // 10 * 10

print(ans)

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

using namespace std;

int main()
{
  	int N;
  	cin >> N;
  	vector<int> L(2*N);
  	for(int i = 0; i < 2*N;i++){
      	cin >> L.at(i);
    }
  	sort(L.begin(), L.end());
  	int ans =0;
  	for(int i = 0; i < N; i++){
      	ans += L.at(2*i);
    }
  	cout << ans;
  	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) (x).begin(), (x).end()

using namespace __gnu_pbds;
using namespace std;

using ull = unsigned long long;
using ll = long long;
using ld = long double;
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int inf = INT_MAX;

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

    int k;
    cin >> k;

    int cur = 7 % k;

    for (int i = 1; i <= k; i++) {
        if (!cur) {
            cout << i << "\n";
            return 0;
        }
        cur = (cur * 10 + 7) % k;
    }

    cout << "-1\n";
    return 0;
}

Measured memory_bytes: 3612
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let n = read::<i64>();
  let t = read::<i64>();
  let mut t_vec = vec![];


  for _ in 0..n {
    t_vec.push(read::<i64>())
  }

  let mut total = t;
  let mut nokori = 0;

  for i in 1..t_vec.len() {
    let current = t_vec[i];
    let prev = t_vec[i - 1];
    total += t;
    if current - prev < t {
      nokori += t - (current - prev).abs();
    }

  }

  println!("{}", total - nokori);
}

Measured memory_bytes: 6396
#include <stdio.h>
#define N_MAX 10000
#define Q_MAX 500

int main(){
  int n,q,S[N_MAX],T[Q_MAX],i,j,cnt=0;
  scanf("%d",&n);
  for(i = 0;i < n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i = 0;i < q;i++){
    scanf("%d",&T[i]);
    for(j = 0;j < n;j++){
      if(T[i] == S[j]){
	cnt++;
	break;
      }
    }
  }
  printf("%d\n",cnt);
  return 0;
  
}



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

int n, p;
int d[200];
char c[200];

int solve(){
    if('0' <= c[p] && c[p] <= '9') return c[p++] - '0';
    int k = p;
    int res = (c[k] == '*' ? 1 : 0);
    p++;
    while(d[p] == d[k] + 1){
        if(c[k] == '+') res += solve();
        if(c[k] == '*') res *= solve();
    }
    return res;
}

int main(){
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;
        rep(i, 0, 200) d[i] = 0;
        rep(i, 0, n){
            string s;
            cin >> s;
            d[i] = s.size();
            c[i] = s[s.size() - 1];
        }
        p = 0;
        cout << solve() << endl;
    }
}

Measured memory_bytes: 3048
/* 選択ソート

   最小値を選択する

   selectionSort(A, N) //N個の要素を含む0オリジンの配列A
   for i が 0 から N-1まで
      minj = i
      for j が i から N-1まで
         if A[j] < A[minj]
            minj = j
         A[i]とA[minj]を交換

   数列Aを読み込み、選択ソートで昇順に並び替え、出力するプログラム
   実際に値が交換された回数を出力

*/

#include <stdio.h>

int selectionSort(int a[], int n)
{
   int count = 0;
   int minj = 0;
   int temp = 0;

   for (int i = 0; i < n-1; i++) {
      minj = i;

      for (int j = i; j <= n-1; j++) {
         if (a[j] < a[minj]) {
            minj = j;
         }
      }
      if (i != minj) {
         temp = a[i];
         a[i] = a[minj];
         a[minj] = temp;
         count++;
      }     
   }
   return count;
}


int main()
{
   int n;
   scanf("%d", &n);

   int a[n];
   for (int i = 0; i < n; i++)
      scanf("%d", &a[i]);

   int count = 0;

   count = selectionSort(a, n);

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

   printf("%d\n", count);

   return 0;
}


Measured memory_bytes: 2112
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(a-b > 0){
		printf("a > b\n");
	}else if(a-b == 0){
		printf("a == b\n");
	}else if(a-b < 0){
		printf("a < b\n");
	}
}



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


int main (){
    long long int r=0,g=0,b=0,ng=0,n;
    string s;
    cin >> n >> s;
    for(int i = 0;i<n;i++){
        if(s[i]=='R'){
            r++;
        }
        if(s[i]=='G'){
            g++;
        }
        if(s[i]=='B'){
            b++;
        }
    }

    for(int i=1;i<=n/2;i++){
        for(int j=0;j<n-2*i;j++){
            if(s[j]!=s[j+i] && s[j]!=s[j+2*i] && s[j+i]!=s[j+2*i]){
                ng++;
            }
        }
    } 
    cout << r*g*b-ng<<endl;      

    return 0;
}


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

int main()
{
	int n;
	cin>>n;
	int a[n+1],sum=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n);
	if(a[n-1]<sum-a[n-1])cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int ans =0;
    for (int i = a; i <= b; i++)
    {
      String as = Integer.toString(i);
      List<String> list=Arrays.asList(Integer.toString(i).split(""));
      Collections.reverse(list);
      String[] bs = (String[]) list.toArray(new String[list.size()]);
      String strb = String.join("", bs);
      if (as.equals(strb))
        ans++;
    }
    System.out.println(ans);
  }
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll inf = 1e6+5;
typedef pair<int, bool> pib;

int main() {
    int a,b,c; cin >> a >> b >> c;
    if (((a*100) + (b*10) + c) %4 == 0){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if (a > b) {
			int d;
			d = b;
			b = a;
			a = d;
		}
		if (b > c) {
			int d;
			d = c;
			c = b;
			b = d;
		}
		if (a > b) {
			int d;
			d = b;
			b = a;
			a = d;
		}
		System.out.println(a + " " + b + " " + c);
	}
}


Measured memory_bytes: 26188
import java.util.Scanner;

class Main{
	public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
		int cnt, m;
		for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
		cnt = 0;
		int x = 4;
		int c = 1;
		int d = 3;
		while(true){
			if(n/x == 0 || x == 3){
				break;
			}
			d *= 3;
			x += d;
			c += 1;
		}
		m = c;
		System.out.println(m);
		
		int G[] = new int[m];
		int touhi = 3;
		G[m-1] = 1;
		for(int i = m-2; i >= 0; i--){
			G[i] = G[i+1]+touhi;
			touhi *= 3;
		}
		for(int i = 0; i < m; i++){
			System.out.print(G[i]+" ");
		}
		System.out.println("");
		
		for(int k = 0; k < m; k++){
			cnt = insertion(a, n, G[k], cnt);
		}
		System.out.println(cnt);
		for(int i = 0; i < n ; i++){
			System.out.println(a[i]);
		}
	}
    	
	private static int insertion(int a[], int n, int g, int cnt){
		for(int i = g; i < n; i++){
        	int v, j;
            v = a[i];
            j = i - g;
            while(j >= 0 && a[j] > v){
                a[j+g] = a[j];
                j = j - g;
            	cnt++;
            }
            a[j+g] = v;
        }
		return cnt;
    }
}


Measured memory_bytes: 299604
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	x := readInt()
	a := readInt()
	if x < a {
		fmt.Println(0)
	} else {
		fmt.Println(10)
	}
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	i, e := strconv.Atoi(read())
	if e != nil {
		panic(e)
	}
	return i
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set> 
#include <algorithm>
#include <vector>
#include <queue>
#include <stdio.h> 
#include <cstdio>
using namespace std;
int main()
{
int N,a,cnt=0;
cin>>N;
int t,x,y;
for(int i=1;i<=N;i++){
cin>>t>>x>>y;
a=t-x-y;
if(a%2==0&&a>=0)
cnt++;}
if(cnt==N)
cout<<"Yes";
else cout<<"No"; 
system ("pause");
return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

ll dp[MX];

int main() {
  int n,w;
  scanf("%d%d",&n,&w);
  rep(i,n) {
    int a,b;
    scanf("%d%d",&a,&b);
    drep(j,w-a+1) {
      maxs(dp[j+a], dp[j]+b);
    }
  }
  cout<<dp[w]<<endl;
  return 0;
}






















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

template <int mod>
struct ModInt {
  int x;
  ModInt(): x(0) {}
  ModInt(long long a) { x = a % mod; if (x < 0) x += mod; }
  ModInt &operator+=(ModInt that) { x = (x + that.x) % mod; return *this; }
  ModInt &operator-=(ModInt that) { x = (x + mod - that.x) % mod; return *this; }
  ModInt &operator*=(ModInt that) { x = (long long) x * that.x % mod; return *this; }
  ModInt &operator/=(ModInt that) { return *this *= power(that, mod - 2); }
  #define op(o, p) ModInt operator o(ModInt that) { return ModInt(*this) p that; }
    op(+, +=) op(-, -=) op(*, *=) op(/, /=)
  #undef op
  friend ostream& operator<<(ostream &os, ModInt m) { return os << m.x; }
};

using mint = ModInt<1000000007>;

template <typename T>
T permutation(int n, int k) {
  T ret = 1;
  for (int i = 0; i < k; i++) {
    ret *= (T) n - i;
  }
  return ret;
}

int main() {
  int n, k; cin >> n >> k;
  cout << permutation<mint>(k, n) << '\n';
  return 0;
}



Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <string>
#define FIN freopen("inputs.txt", "r", stdin)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;

// int dp[1000];
int main(){
  ll H;
ll ans = 0;
//FIN;
    cin>>H;
    while(H){
        H >>= 1;
        ans = 2 * ans + 1;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int n,k; cin >> n >> k;
  int ans = 0;
  vector<int> f(n);
  rep(i,n) cin >> f[i];
  sort(f.begin(), f.end());
  rep(i,k) ans += f[i];
  cout << ans << endl;
}

Measured memory_bytes: 3596
#include <iostream>

using namespace std;
int main() {
    int N, K;
    string S;

    cin >> N >> K;
    cin >> S;

    int switch_point = 1;
    int start_point = 0;
    char s;
    for (int i = 0; i < N; i++) {
        if (i == 0)
            s = S[i];
        else {
            if (s == S[i])
                start_point += 1;
            else {
                switch_point += 1;
                s = S[i];
            }
        }
    }

    if (switch_point % 2 == 0) {
        if (switch_point / 2 > K)
            cout << start_point + 2 * K << endl;
        else
            cout << N - 1 << endl;
    }
    else {
        if (switch_point / 2 >= K)
            cout << start_point + 2 * K << endl;
        else
            cout << N - 1 << endl;
    }
}

Measured memory_bytes: 512
while 1:
    H,W=[int(i) for i in input().split()]
    if H==W==0:
        break
    else:
        if W<=2:
            for i in range(H):
                for s in range (W):
                    print("#",end="")
                print('')
            print('')
        else:
            for s in range(W):
                print("#",end="")
            print('')
            for i in range(H-2):
                print('#',end="")
                for s in range (W-2):
                    print(".",end="")
                print('#',end="")
                print('')
            for s in range(W):
                print("#",end="")
            print('')
        print('')

Measured memory_bytes: 9024
#include <stdio.h>

int main(){
    int A,B,C;
    int sum,sub,mul,max;
    scanf("%d %d",&A,&B);
    sum = A + B;
    sub = A - B;
    mul = A * B;
    if((sum > sub)&&(sum > mul)){
        max = sum;
    }else if((sub > sum) && (sub > mul)){
        max = sub;
    }else if((mul > sum) && (mul > sub)){
        max = mul;
    }
    printf("%d\n",max);
    return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<Edge>> edges = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			String str[] = br.readLine().split(" ");
			edges.add(new ArrayList<>());
			for (int j = 0; j < n; j++) {
				int a = Integer.parseInt(str[j + 1]);
				if (a == -1)
					a = Integer.MAX_VALUE;

				edges.get(i).add(new Edge(j, a));
			}
		}

		int ans = prime(edges, n);
		System.out.println(ans);
	}

	static int prime(ArrayList<ArrayList<Edge>> edges, int n) {
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean used[] = new boolean[n];

		int sum = 0;

		pq.add(new Edge(0, 0));

		while (!pq.isEmpty()) {
			Edge e = pq.poll();

			if (used[e.to])
				continue;

			used[e.to] = true;
			sum += e.cost;
			pq.addAll(edges.get(e.to));
		}
		return sum;
	}
}

class Edge implements Comparable<Edge> {
	int to;
	int cost;

	public Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}


Measured memory_bytes: 28448
const [head, ...squares] = require('fs').readFileSync('/dev/stdin', 'utf8').split(/\n/)
const [h, w, k] = head.split(/\s/).map(Number)
let result = 0
const rawConditions = createConditions(h), columnConditions = createConditions(w)
for (const rawCondition of rawConditions) {
  for (const columnCondition of columnConditions) {
    let count = 0
    for (let r = 0; r < h; r++) {
      for (let c = 0; c < w; c++) {
        if (squares[r][c] === '#' && !rawCondition.includes(r) && !columnCondition.includes(c)) {
          count += 1
        }
      }
    }
    if (count === k) {
      result += 1
    }
  }
}
console.log(result)

function createConditions(l, result = [[]]) {
  if (l === 0) {
    return result
  }
  l -= 1
  const next = []
  for (const r of result) {
    next.push(r)
    next.push([...r, l])
  }
  return createConditions(l, next)
}

Measured memory_bytes: 32876
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int r = Integer.parseInt(sc.next());

		if (n < 10) {
			System.out.println(r + (100 * (10 - n)));
		} else {
			System.out.println(r);
		}
	}
}


Measured memory_bytes: 21972