akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define Yes()           printf("Yes\n")
#define No()            printf("No\n")
#define YES()           printf("YES\n")
#define NO()            printf("NO\n")
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  int a, b, c; cin >> a >> b >> c;
  if (a == b && b == c) Yes();
  else No();
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 888
#![allow(unused_imports)]
#![allow(dead_code)]
use datastructure::*;
use grapth::*;
use input_scanner::*;
use math::*;
use string_algorithm::*;
use util::*;

use std::cmp;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};

fn main() {
    let mut scan = Scanner::new();
    let h: usize = scan.next();
    let w: usize = scan.next();
    let k: usize = scan.next();
    let mut c: Vec<Vec<u8>> = vec![];

    for i in 0..h {
        c.push(scan.next_word());
    }

    let mut ans = 0;
    for i in 0..(1<<h){
        for j in 0..(1<<w) {
            let mut cnt = 0;
            for y in 0..h {
                for x in 0..w {
                    if c[y][x] == '#' as u8 && (i>>y&1) == 0 && (j>>x&1)==0{
                        cnt+=1;
                    }
                }
            }
            if cnt == k {
                ans += 1;
            }
        }
    }


    println!("{}", ans);
}

mod datastructure {}
mod grapth {}
mod math {}
mod string_algorithm {}
mod util {}
mod input_scanner {
    pub struct Scanner {
        bytes: Vec<u8>,
        begin: usize,
        end: usize,
    }

    impl Scanner {
        pub fn new() -> Self {
            use std::io::Read;
            let mut buffer: Vec<u8> = Vec::new();
            std::io::stdin().read_to_end(&mut buffer).unwrap();
            let end = (0..buffer.len())
                .find(|i| buffer[*i].is_ascii_whitespace())
                .unwrap_or(buffer.len());
            Scanner {
                bytes: buffer,
                begin: 0,
                end: end,
            }
        }
        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            let s: &str =
                unsafe { std::str::from_utf8_unchecked(&self.bytes[self.begin..self.end]) };
            let ret: T = s.parse::<T>().ok().expect("Parse error.");
            self.skip();
            ret
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
        pub fn next_word(&mut self) -> Vec<u8> {
            let r = Vec::from(&self.bytes[self.begin..self.end]);
            self.skip();
            r
        }
        fn skip(&mut self) {
            self.begin = (self.end..self.bytes.len())
                .find(|i| !self.bytes[*i].is_ascii_whitespace())
                .unwrap_or(self.bytes.len());
            self.end = (self.begin..self.bytes.len())
                .find(|i| self.bytes[*i].is_ascii_whitespace())
                .unwrap_or(self.bytes.len());
        }
    }
}


Measured memory_bytes: 2136
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int N, L;
  cin >> N >> L;
  string S[110];
  string str;

  for(int i=0; i<N; ++i)
    cin >> S[i];

  sort(S, S+N);

  for(int i=0; i<N; ++i)
    str += S[i];

  cout << str << endl;

  return 0;
}


Measured memory_bytes: 256
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	a := (readInt() + 11) % 13
	b := (readInt() + 11) % 13
	if a < b {
		println("Bob")
	} else if b < a {
		println("Alice")
	} else {
		println("Draw")
	}
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
class G {
public:
  vector<vector<int>> p, inv, sp, sinv;
  int n, m;
  vector<int> b, c, depth;
  vector<bool> a;
  G(int nn, vector<vector<int>> &np, vector<vector<int>> &ninv) {
    n = nn;
    p = np;
    inv = ninv;
    a.resize(n);
    c.resize(n);
    for (int i = 0; i < n; i++)
      c[i] = -1;
  }
  void dfs(int i) {
    if (a[i])
      return;
    a[i] = true;
    for (auto &j : p[i]) {
      if (a[j])
        continue;
      dfs(j);
    }
    b.push_back(i);
  }
  void dfs2(int i, int id) {
    if (c[i] > -1)
      return;
    c[i] = id;
    for (auto &j : inv[i]) {
      if (c[j] > -1)
        continue;
      dfs2(j, id);
    }
  }
  void solve() {
    for (int i = 0; i < n; i++)
      dfs(i);
    int j = 0;
    for (int i = n - 1; i >= 0; i--) {
      if (c[b[i]] > -1)
        continue;
      dfs2(b[i], j++);
    }
    m = j;
    sp.resize(m);
    sinv.resize(m);
    vector<set<int>> sps(m);
    for (int i = 0; i < n; i++) {
      for (int &j : p[i]) {
        if (c[i] == c[j])
          continue;
        sps[c[i]].insert(c[j]);
      }
    }
    for (int i = 0; i < m; i++) {
      for (auto &j : sps[i]) {
        sp[i].push_back(j);
        sinv[j].push_back(i);
      }
    }
  }
};

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0)
      break;
    vector<vector<int>> p(n), inv(n);
    vector<double> z(n);
    for (int i = 0; i < n; i++) {
      cin >> z[i];
      int m;
      cin >> m;
      for (int j = 0; j < m; j++) {
        int k;
        cin >> k;
        k--;
        p[i].push_back(k);
        inv[k].push_back(i);
      }
    }
    G g(n, p, inv);
    g.solve();

    int m = g.m;
    vector<double> z2(m);
    for (int i = 0; i < m; i++) {
      z2[i] = 1.;
    }
    for (int i = 0; i < n; i++) {
      z2[g.c[i]] *= z[i];
    }
    double ans = 1.;
    for (int i = 0; i < m; i++) {
      if (g.sinv[i].size() == 0) {
        ans *= (1. - z2[i]);
      }
    }
    printf("%.9lf\n", ans);
  }
  return 0;
}


Measured memory_bytes: 3372
function Main(input) {
  var N = input.trim();
  var l = N.length;
  N = parseInt(N, 10);
  var ans;
  if (N <= 10 ) {
    ans = Math.min(9, N);
  } else {
    ans = 9;
    var tmpX;
    var tmpY;

    for (var i = 1; i <=9 ;i++){
      for (var j = 1; j<=i; j++){
        if (i == j){
          tmpX = 0;
          basic_loop:
          for (var k = 0; k < (l - 1); k++){
            for (var middle = 0; middle < Math.pow(10, k); middle ++){
              if (i * Math.pow(10, k + 1) + middle * 10 + j <= N) tmpX ++;
              else break basic_loop;
            }
          }
          ans += (tmpX + 1) * (tmpX + 1) - 1;
        } else {
          tmpX = tmpY = 0;
          basic_loop2:
          for (var k = 0; k < (l - 1); k++){
            for (var middle = 0; middle < Math.pow(10, k); middle ++){
              if (i * Math.pow(10, k + 1) + middle * 10 + j <= N) tmpX ++;
              else break basic_loop2;
            }
          }
          basic_loop3:
          for (var k = 0; k < (l - 1); k++){
            for (var middle = 0; middle < Math.pow(10, k); middle ++){
              if (j * Math.pow(10, k + 1) + middle * 10 + i <= N) tmpY ++;
              else break basic_loop3;
            }
          }
          ans += tmpX * tmpY * 2;
        }

      }
    }
  }
  console.log(ans);
}
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

using namespace std;
// ax + by = gcd(a, b)
long long extended_euclidean(long long a, long long b, long long &x, long long &y)
{
	x = 1;
	y = 0;
	long long u = 0, v = 1;
	long long ri = a, rj = b, rk, k;

	// [x y]
	// [u v]
	while (1) {
		k = ri/rj;
		rk = ri%rj;
		ri = rj;
		rj = rk;


		// [newx newy] = [0  1] [x y]
		// [newu newv] = [1 -k] [u v]
		long long newx, newy, newu, newv;
		newx = u;
		newy = v;
		newu = x-k*u;
		newv = y-k*v;
		x = newx;
		y = newy;
		u = newu;
		v = newv;

		if (rk == 0)
			break;
	}

	return a*x+b*y; // gcd
}

int main(void)
{
	int a, b;
	cin >> a >> b;
	long long x, y;
	long long d = extended_euclidean(a, b, x, y);
	cout << a / d * b << endl;
	return 0;
}

Measured memory_bytes: 3584
n=int(input())
l=list(map(int,input().split()))
curr=1000
st=0
i=0
while i<n-1:
    if(l[i]<l[i+1]):
        st=curr//l[i]
        curr=curr-st*l[i]
        j=i
        while j<n-1 and l[j+1]>=l[j]:
            j+=1
        curr+=st*l[j]
        st=0
        i=j+1
    else:
        i+=1
print(curr)

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

int main(){
    int r;
    cin >> r;
    
    double ans = 2*r*3.1415;
    
    cout << ans << endl;
}

Measured memory_bytes: 3780
#include<stdio.h>

int rec(int,int);

int n,A[20],M;

int main(void){
  int q;
  int i;

  scanf("%d",&n);

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

  scanf("%d",&q);

  for(i=0;i<q;i++){
    scanf("%d",&M);
    
    if(rec(0,0)==1) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}


int rec(int sum,int cnt){
  if(cnt==n){
    if(M==sum) return 1;
    else return 0;
  }
  else{
    if(rec(sum+A[cnt],cnt+1)==1 || rec(sum,cnt+1)==1){
      return 1;
    }
    else{
      return 0;
    }
  }
}

Measured memory_bytes: 580
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 10 ** 9 + 7

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]
    fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]
    fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]
    finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]
    finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    comb = fac[a] * finv[b] % mod * finv[a - b] % mod
    return comb


def nPr(a, b):
    comb = fac[a] * finv[a - b] % mod
    return comb


n, m = map(int, input().split())

res = 0
for i in range(n + 1):
    res += nCr(n, i) * (-1) ** i * nPr(m - i, n - i)
    res %= mod
print(res * nPr(m, n) % mod)


Measured memory_bytes: 50148
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

void solve(){
    int n,m;
    cin >> n >> m;
    vector<ld>a(n);
    for(int i = 0;i<n;i++) cin >> a[i];
    ld sum = 0; ld maxi = 0;
    for(int i = 0;i<m;i++) sum += a[i];
    maxi = sum;
    for(int i = m;i<n;i++){
        sum -= a[i-m];
        sum += a[i];
        maxi = max(sum,maxi);
    }
    maxi += m;
    maxi /= 2;
    cout << fixed <<setprecision(20)<<maxi;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


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

typedef long long ll;
#define PI 3.1415926535897932384626433
#define mod 1000000007

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int lcm(int a, int b) { return a * b / gcd(a, b); }

int main(){
    int n;
    cin >> n;
    int l[2*n];
    for (int i = 0; i < 2*n; i++){
        cin >> l[i];
    }
    sort(l, l + 2*n, greater<int>());
    ll ans = 0;
    for (int i = 0; i < 2*n; i += 2){
        ans += min(l[i], l[i + 1]);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define F first
#define S second
#define lp(i, a, b) for (int i=a;i<=(int)b;++i)
#define lp2(i, a, b) for (ll i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define pr(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define vii vector<pii>
#define vll vector<pll>
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define clr(c, x) memset(c,x,sizeof(c));
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int N = (int) 1e6 + 5;
const ll mod = 998244353;
deque<int> dq;
int n, m, vv, p;

inline bool can(int mid) {
    if (dq[mid] + m < dq[p]) return false;
    ll sum = m * 1LL * (p - 1);
    sum += (n - mid + 1) * 1LL * m;
    lp(i, p, mid - 1) sum += dq[mid] + m - dq[i];
    return sum >= m * 1LL * vv;
}

int main() {
    FAST;
    cin >> n >> m >> vv >> p;
    lp(i, 1, n) {
        int x;
        cin >> x;
        dq.pb(x);
    }
    sort(allr(dq));
    dq.pf(0);
    int cnt = 0, l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (can(mid)) {
            l = mid + 1;
            cnt = mid;
        } else r = mid - 1;
    }
    cout << cnt << "\n";
    return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 1 1
2
0 1 4 1
3 0 3 3

output:
1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000
"""

import sys
import math


class Segment(object):
    __slots__ = ('source', 'target')

    def __init__(self, source, target):
        self.source = complex(source)
        self.target = complex(target)


class Circle(object):
    __slots__ = ('centre', 'radius')

    def __init__(self, x, y, r):
        self.centre = x + y * 1j
        self.radius = r


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def get_cross_point(c, l):
    prj_vector = project(l, c.centre)
    line_unit_vector = (l.target - l.source) / (abs(l.target - l.source))
    base = math.sqrt(pow(c.radius, 2) - pow(abs(prj_vector - c.centre), 2))
    p1, p2 = prj_vector + line_unit_vector * base, prj_vector - line_unit_vector * base

    if p1.real < p2.real:
        ans = (p1, p2)
    elif p1.real == p2.real:
        if p1.imag < p2.imag:
            ans = (p1, p2)
        else:
            ans = (p2, p1)
    else:
        ans = (p2, p1)
    return ans


def solve(_lines):
    for line in _lines:
        line_axis = tuple(map(int, line))
        p0, p1 = (x + y * 1j for x, y in zip(line_axis[::2], line_axis[1::2]))
        l = Segment(p0, p1)
        cp1, cp2 = get_cross_point(circle, l)
        print('{0:.8f} {1:.8f} {2:.8f} {3:.8f}'.format(cp1.real, cp1.imag, cp2.real, cp2.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    cx, cy, radius = map(int, _input[0].split())
    q_num = int(_input[1])
    lines = map(lambda x: x.split(), _input[2:])

    circle = Circle(cx, cy, radius)
    solve(lines)

Measured memory_bytes: 7908
from heapq import heapify, heappop, heappush

x, y, a, b, c = map(int, input().split())

p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
r = [-x for x in r]

p.sort()
q.sort()
r.sort()

p = p[-x:]
q = q[-y:]

heapify(p)
heapify(q)
heapify(r)

is_p = True
is_q = True

while is_p and is_q and r:
    pp = heappop(p)
    qq = heappop(q)
    rr = heappop(r)

    if pp <= qq:
        heappush(q, qq)
        if pp < -rr:
            heappush(p, -rr)
        else:
            is_p = False
            heappush(p, pp)
            heappush(r, rr)
    else:
        heappush(p, pp)
        if qq < -rr:
            heappush(q, -rr)
        else:
            is_q = False
            heappush(q, qq)
            heappush(r, rr)

print(sum(p) + sum(q))

Measured memory_bytes: 23456
def gcd(m,n):
  if n == 0:
    return m
  else:
    r = m % n
    return gcd(n,r)
  
def LCM(num1,num2):
  return (num1/gcd(num2,num1))*num2

N = input()
l = []
for i in range(N):
  l.append(input())
l.sort()
lcm = l[N-1]
for i in range(N-1):
  lcm = LCM(l[N-2-i],lcm)
print lcm

Measured memory_bytes: 2568
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
    int a,b;
    string res = "Yes";
    cin >> a >> b;
    if(a % 2 == 0 || b % 2 == 0) res = "No";
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

m = max(a)
idxs = [i for i, v in enumerate(a) if v == m]

if len(idxs) > 1:
    for i in range(n):
        print(m)

if len(idxs) == 1:
    idx = idxs[0]
    for i in range(n):
        if idx == i:
            _a = a.copy()
            _a.pop(i)
            print(max(_a))
        else:
            print(m)


Measured memory_bytes: 20456
import java.util.*;
public class Main {

    public static void main(String __[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        int equal_checker = 1;
        double total = 0;
        int total_cost = 0;
        for(int x = 0; x<N; x++){
            a[x]= sc.nextInt();
            total += a[x];
        }


            double equal_integer = (Math.round(total / N));
            for(int y : a){
                total_cost += Math.pow((y- equal_integer),2);
            }
            System.out.println(total_cost);

    }
}


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define int long long int
#define maxn 100
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

int mpow(int N, int P, int M)  //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0) {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

int counter(int x) {           //bit計算
    if (x == 0) return 0;
    return counter(x >> 1) + (x & 1);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

bool IsPrime(int num) {   //素数判定
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

signed main() {
    float inf = std::numeric_limits<float>::infinity();
    double N;
    cin >> N;
    for (double h = 1; h <= 3500; h += 1) {
        for (double n = 1; n <= 3500; n += 1) {
            double w;
            w = (N * h) / (4 * h * n - N * (h + n)) * n;
            if (ceil(w) == floor(w) && (w != inf) && (w >= 0)) {
                cout << h << " " << n << " " << fixed << setprecision(10) <<(int) w << " " << endl;
                return 0;
            }
        }
    }
}


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

int main(void)
{
    int a , b, c, d ;
    
    scanf("%d", &a);  scanf("%d", &b); scanf("%d", &c); scanf("%d", &d);
    
    if(abs(a - c) <= d )
    {
        printf("Yes");
    }
    else if (abs(a - b) <= d )
    {
        if (abs(b - c) <= d )
        {
            printf("Yes");
        }
        else
        {
            printf("No");
        }
    }
    else 
    {
        printf("No");
    }
    
    
    return 0 ;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rem(i, m, n) for (int i = m; i < (n); i++)
#define eps (1e-7)
#define inf (1e9)
#define pi (acos(-1))
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

bool compare(const pair<string, int> &x, const pair<string, int> &y)
{
    return x.second > y.second;
}

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

    int n;
    cin >> n;
    vector<pair<string, int> > p;
    rep(i, n)
    {
        string s;
        cin >> s;

        bool flag = true;
        for (auto &e : p)
        {
            if (s == e.first)
            {
                e.second++;
                flag = false;
                break;
            }
        }
        if (flag)
            p.push_back(make_pair(s, 1));
    }
    int m;
    cin >> m;
    rep(i, m)
    {
        string s;
        cin >> s;

        bool flag = true;
        for (auto &e : p)
        {
            if (s == e.first)
            {
                e.second--;
                flag = false;
                break;
            }
        }
        if (flag)
            p.push_back(make_pair(s, -1));
    }

    sort(p.begin(),
         p.end(),
         compare);

    cout << max(0, p[0].second) << "\n";

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int top,S[1000];
void push(int x)
{
  S[++top] = x;
}
int pop()
{
  top--;
  return S[top+1];
}
int main ()
{
  int a,b;
  char s[100];
  top = 0;
  while (scanf("%s",s)!=EOF)
  {
    if(s[0] == '+')
    {
      a = pop();
      b = pop();
      push(a+b);
    }
    else if(s[0]=='-')
  {    b = pop();
      a = pop();
      push(a-b);
  }
  else if(s[0] == '*')
  {
      a = pop();
      b = pop();
      push(a*b);
  }
  else push(atoi(s));
  }
  printf("%d\n",pop());
  return 0 ;
}




Measured memory_bytes: 3216
package main

import (
	"fmt"
)

func main() {
	var str string
	rts := []string{}

	fmt.Scan(&str)
	for _, r := range str {
		rts = append([]string{string(r)}, rts...)
	}

	for _, v := range rts {
		fmt.Print(v)
	}
	fmt.Println()
}



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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

 int main(){
int X, Y, Z, K;
cin >> X >> Y >> Z >> K;

vector<ll> A(X), B(Y), C(Z);
REP(i, X) cin >> A.at(i);
REP(i, Y) cin >> B.at(i);
REP(i, Z) cin >> C.at(i);

vector<ll> ans;
REP(i, X)REP(j, Y) ans.push_back(A.at(i) + B.at(j));

sort(all(ans));
reverse(all(ans));

vector<ll>an;
REP(i, min(K, (int)ans.size()))REP(j, Z){
  an.push_back(ans.at(i) + C.at(j)); 
}

sort(all(an));
reverse(all(an));

REP(i, K) print(an.at(i));

 }

Measured memory_bytes: 42856
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define MOD 1000000007
#define all(c) c.begin(), c.end()
#define peek(v)      \
	for (auto i : v) \
		cout << i << ' ';

void solve()
{
	ll n;
	cin >> n;
	ll minn = log10(n) + 1;
	for (ll i = 1; i * i <= n; i++)
	{
		if (n % i != 0)
			continue;
		ll m = n / i;
		ll d = max(log10(i) + 1, log10(m) + 1);
		if (d < minn)
			minn = d;
	}
	cout << minn;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	cerr << "\n\n~" << 500 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Measured memory_bytes: 512
///   ***   ---   |||         In the name of ALLAH        |||   ---   ***   ///



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


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}


int main()
{
    optimize();

    ll n, two = 0, five = 0, ten = 0;
    cin >> n;
    if ( n % 2 ) return cout << 0 << endl, 0;
    ll tmp = n >> 1;

    while ( tmp > 0 ) {
        two += ( tmp >> 1 );
        tmp >>= 1;
    }
    tmp = n >> 1;

    while ( tmp > 0 ) {
        five += ( tmp / 5 );
        tmp /= 5;
    }


    cout << min ( two, five ) << endl;

    return 0;
}


















Measured memory_bytes: 256
n,t = map(int, input().split())
a = []
b = 0
for i in range(n):
  l = list(map(int, input().split()))
  a.append(l)
a.sort()
for i in range(n):
  if a[i][1] <= t:
    b = a[i][0]
    break
if b > 0:
  print(b)
else:
  print("TLE")


Measured memory_bytes: 3060
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  int a[4], b[4];
  while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1]>>b[2]>>b[3]) {
    int num[10]; CLR(num);
    int hit = 0, blow = 0;
    FOR(i,0,4) {
      if(a[i] == b[i]) hit++;
      num[a[i]]++;
      num[b[i]]++;
    }
    FOR(i,0,10) if(num[i] > 1) blow++;
    cout << hit << " " << blow - hit << endl;
  }
  return 0;
}

Measured memory_bytes: 2956
#include <bits/stdc++.h>
using namespace std;
int h, w, k;	
int cut[12];
int sum[12][1002];
int ans = 1e9 + 1;

bool ok(int siz, int l, int r){
	cut[siz + 1] = h;
	for (int i = 1; i <= siz + 1; ++i){
		int he = cut[i];
		int tot = sum[cut[i]][r] - sum[cut[i - 1]][r] - sum[cut[i]][l] + sum[cut[i - 1]][l];
		if (tot > k){
			return false;
		}
	}
	return true;
}

void solve(int now, int siz){
	if (now == h){
		int l = 0;
		int tmp = siz;
		for (int i = 1; i <= w; ++i){
			if (!ok(siz, l, i)){
				l = i - 1;
				tmp++;
			}
		}
		if (ok(siz, w - 1, w)){
			ans = min(ans, tmp);
		}
		return;
	}
	solve(now + 1, siz);
	cut[siz + 1] = now;
	solve(now + 1, siz + 1);
}



int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	cin >> h >> w >> k;
	for (int i = 1; i <= h; ++i){
		for (int j = 1; j <= w; ++j){
			char c;
			cin >> c;
			int now = c - '0';
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + now;
		}
	}
	solve(1, 0);
	cout << ans;
	return 0;
}



Measured memory_bytes: 256
#include<iostream>

class GetInput
{
protected:
	int num, sum;
public:
	void getInput();
};

void GetInput::getInput()
{
	std::cin >> num >> sum;
}

class outputCounts :public GetInput
{
protected:
	int cmb1, cmb2, cmb3, way;
public:
	bool judgeEnd();
	void outputCombination();
	void countCombination();

	outputCounts();
	outputCounts(int n, int s);
};

outputCounts::outputCounts(int n, int s)
{
	num = n;
	sum = s;
}

outputCounts::outputCounts()
{

}

bool outputCounts::judgeEnd()
{
	if (num == 0 && sum == 0)
	{
		return false;
	}
	else
	{
		return true;
	}
}

void outputCounts::outputCombination()
{
	way = 0;

	for (int i = 1;i <= (num - 2);i++)
	{
		cmb1 = i;
		for (int j = i + 1;j <= (num - 1);j++)
		{
			cmb2 = j;
			for (int k = j + 1;k <= num;k++)
			{
				cmb3 = k;

				countCombination();
			}
		}
	}
	std::cout << way << std::endl;
}

void outputCounts::countCombination()
{

	if ((cmb1 + cmb2 + cmb3) == sum)
	{
		way++;
	}
}

int main()
{
	outputCounts op;

	while (true)
	{
		op.getInput();

		if (op.judgeEnd() == false)
		{
			break;
		}

		op.outputCombination();

	}

	return 0;
}


Measured memory_bytes: 3080
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w, &h, &x, &y, &r);
	if (w < x || x < 0) {
		printf("No\n");
		return 0;
	}
	if (h < y || y < 0) {
		printf("No\n");
		return 0;
	}

	if (((0 <= x - r) && (x + r) <= w)
		&& ((0 <= y - r) && (y + r) <= h)) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 2684
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main() {
    map<string,int>t;
    int n;
    cin>>n;
    string a,b;
    while(n--){
        cin>>a>>b;
        if(a=="insert"){
            t[b]=1;
        }else{
            if(t[b]==0){
                cout<<"no"<<endl;
            }else{
                cout<<"yes"<<endl;
            }
        }
    }
}

Measured memory_bytes: 52520
n, m, k = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for  i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i] + B[i])

ans, j = 0, m
for i in range(n+1):
    if a[i]>k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)

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

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

    bool change = false;
    int m = INT_MAX;
    int diff = 0;
    int pairs = 0;
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        if (m > a) {
            m = a;
            change = true;
        } else { // m < a
            if (diff < abs(a - m)) {
                diff = abs(a - m);
                pairs = 1;
                change = false;
            } else if (diff == abs(a - m) && change) {
                pairs++;
                change = false;
            }
        }

    }

    cout << pairs << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

		long X = scan.nextLong();
		long m = 100;
		int ans = 0;

		while(true) {
			m *= 1.01;
			ans++;
			if(X <= m) {
				break;
			}
		}

		System.out.println(ans);

	}
}

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

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    string s;cin>>s ;
    int w=0,r=n-1;
    int count = 0 ;
    while(w<=r)
    {
        while(w<n && s[w]=='R') w++ ;
        while(r>=0 && s[r]=='W') r-- ;
        if(w<n && r>=0 && w<r) count++ ;
        w++ ;r-- ;
    }
    cout<<count<<"\n" ;
}

Measured memory_bytes: 3740
package main

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

func NewLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func upTemp(lowTemp int, height int) float64 {
	return float64(lowTemp) - float64(height)*0.006
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	line := NewLine(sc)
	line = NewLine(sc)
	words := strings.Fields(line)
	lowTemp, _ := strconv.Atoi(words[0])
	idealTemp, _ := strconv.Atoi(words[1])
	line = NewLine(sc)
	choices := strings.Fields(line)

	var ans int
	var ansDiff float64 = 1000000000

	for i, choiceStr := range choices {
		choice, _ := strconv.Atoi(choiceStr)
		temp := upTemp(lowTemp, choice)
		diff := math.Abs(float64(idealTemp) - temp)

		if diff < ansDiff {
			ans = i + 1
			ansDiff = diff
		}
	}
	fmt.Printf("%d\n", ans)
}



Measured memory_bytes: 640
#![allow(non_snake_case)]
#[allow(unused_imports)]
use std::io::{self, Write};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
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, usize1) => {
        read_value!($next, usize) - 1
     };
    ($next:expr, isize1) => {
        read_value!($next, isize) - 1
     };
     ($next:expr, $t:ty) => {
         $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(dead_code)]
const MOD: u64 = 1000000007;
#[allow(dead_code)]
fn to_num(c: char) -> i64 {
    c as i64 - 48
}


fn main() {
    input!{
        H: isize, W: isize, N: usize,
        ab: [(isize1, isize1); N],
    }
    let mut hash = HashMap::new();

    for (a, b) in ab {
        for y in 0..3 {
            for x in 0..3 {
                if a - y >= 0 && b - x >= 0 && a - y + 2 < H && b - x + 2 < W {
                    *hash.entry((a - y, b - x)).or_insert(0) += 1;
                }
            }
        }
    }

    let mut count = vec![0; 10];
    for (_, v) in hash {
        count[v] += 1;
    }
    count[0] = (H - 2) * (W - 2) - count.iter().sum::<isize>();
    
    for i in 0..10 {
        println!("{}", count[i]);
    }
}

Measured memory_bytes: 55596
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    long b = sc.nextLong();
    long n = sc.nextLong();
    long max = 0;
    long num = 0;

    long reg = n%b;
    if(n>b){
      n = n-reg-1;
    }else if(n%b==0){
      n = n -1;
    }

    long ans = ((a*n)/b)- a*(n/b);

    System.out.println(ans);


  }
}

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

// 100%は理解できていない
vector<int> zalgo(string s){
    vector<int> prefix(s.size());
    for(int i = 1, j = 0; i < s.size(); i++){
        if(i + prefix[i-j] < j + prefix[j]){
            prefix[i] = prefix[i-j];
        }else{
            int k = max(0, j+prefix[j]-i);
            while(i + k < s.size() && s[k] == s[i+k])   k++;
            prefix[i] = k;
            j = i;
        }
    }
    prefix[0] = s.size();
    return prefix;
}

int main(){
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(int i = 0; i < n; i++){
        vector<int> tmp = zalgo(s.substr(i));
        for(int j = 0; j < n-i; j++){
            if(tmp[j] <= j) ans = max(ans, tmp[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
/*input
5 2 3
*/
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int, int>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	ll n, A, B;
	cin >> n >> A >> B;
	if(A > B)
		swap(A, B);
	ll ans = LLONG_MAX;
	if(A % 2 == B % 2)
		ans = min(ans, (B - A) / 2);
	ll moves = A - 1, bpos = max(1ll, B - moves);
	ans = min(ans, moves + (bpos - 1 + 1) / 2);
	moves = n - B;
	ll apos = min(n, A + moves);
	ans = min(ans, moves + (n - apos + 1) / 2);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    long int K,X;
    cin>>K>>X;
    long int min = X-K+1;
    long int max = X+K-1;
    if(min< -1000000) min = -1000000;
    if(max> 1000000) max = 1000000;
    for (auto i=min;i<=max;i++){
        cout<<i<<" ";
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		double k = Double.parseDouble(sc.next()+sc.next());
		int t = (int)Math.sqrt(k);
		System.out.println(t*t==k ? "Yes" : "No");
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

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

bt, bx, by = 0, 0, 0

for _ in range(N):
    t, x, y = map(int, input().split())
    dist = abs(x-bx)+abs(y-by)
    time = t-bt
    if time<dist or time%2!=dist%2:
        print('No')
        break
    bt, bx, by = t, x, y
else:
    print('Yes')

Measured memory_bytes: 3060
from collections import deque

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[y][x]

H, W = map(int, input().split())

maze = ["#"*(W+2)]
for i in range(H):
    tmp = "#"
    tmp += input()
    tmp += "#"
    maze.append(tmp)
maze.append("#"*(W+2))
    
#for i in range(H+2):
#    print(maze[i])

max_bfs = 0
for sy in range(1, H+2):
    for sx in range(1, W+2):
        if maze[sy][sx] == ".":
            visited = [[-1]*(W+2) for j in range(H+2)]
            tmp_bfs = bfs(maze, visited, sy, sx)
            if tmp_bfs > max_bfs:
                max_bfs = tmp_bfs
        
print(max_bfs)

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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<LP, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

vector<int> dp(10001, 0);

int main(){
	int n, ww;
	cin >> n >> ww;
	vector<int> v(n);
	vector<int> w(n);
	REP(i, n)
		cin >> v[i] >> w[i];
	REP(i, n)
		FORR(j, ww, w[i])
			dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
	cout << *max_element(dp.begin(), dp.begin() + ww + 1) << endl;
	return 0;
}


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

#define N 10001

int main(){
  int loop;
  int Counter[N];
  int  *Before,*After;
  int i;

  
  scanf("%d",&loop);
  
  Before=(int *)malloc(sizeof(int)*loop+1);
  After=(int *)malloc(sizeof(int)*loop+1);
  
  for(i=0;i<N+1;i++){
    Counter[i]=0;
  }

  for(i=1;i<loop+1;i++){
    scanf(" %d",&Before[i]);
    Counter[Before[i]]++;
  }
  
  for(i=1;i<N+1;i++){
    Counter[i]=Counter[i]+Counter[i-1];
  }

  for(i=loop;i>=1;i--){
    After[Counter[Before[i]]]=Before[i];
    Counter[Before[i]]--;
  }

  for(i=1;i<loop;i++){
    printf("%d ",After[i]);
  }

  printf("%d\n",After[loop]);

  free(Before);
  free(After);
  
  return 0;
}





Measured memory_bytes: 17100
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <numeric>
#include <iomanip>
#include <climits>
#include <cstring>
#include <cmath>

using namespace std;

#define int long long
#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 rrep(i, n) for (int i=(int)(n)-1;i>=0;--i)
#define rrep1(i, n) for (int i=(int)(n);i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)(r);++i)
#define rrange(i, l, r) for (int i=(int)(r)-1;i>=l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;
using vpii=vector<pii>;
using ll=long long;

constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}
template<typename T>bool chmin(T&a,T b){return a>b?(a=b,1):0;}
template<typename T>bool chmax(int&a,int b){return a<b?(a=b,1):0;}
int read(){int a;scanf("%lld",&a);return a;}

const double pi = acos(-1);
constexpr int inf = 3*TEN(18) + 10;

int H, W;
int d[10][10];

signed main()
{
	cin >> H >> W;

	rep(i, 10) rep(j, 10) cin >> d[i][j];
	rep(k, 10) rep(i, 10)  rep(j, 10) chmin(d[i][j], d[i][k]+d[k][j]);

	int ans = 0;

	rep(i, H) rep(j, W) {
		int a; cin >> a;
		if (~a) ans += d[a][1];
	}

	cout << ans << endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
ll GCD(ll a, ll b){
    if(b==0) return a;
    else return GCD(b,a%b);
}

int main(){
ll a,b;cin>>a>>b;
ll GCD(ll a,ll b);

cout<<a*b/GCD(a,b)<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <map>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    ll n, w;
    cin >> n >> w;
    ll wi, vi;
    map<ll, vector<ll>> d;
    ll wm;
    for(int i=0; i<n; i++){
        cin >> wi >> vi;
        if(i==0){wm = wi;}
        if(d.find(wi)!=d.end()){
            d[wi].push_back(vi);
        }else{
            d[wi] = {vi};
        }
    }
    vector<ll> l(4, 0);
    for(map<ll, vector<ll>>::iterator it = d.begin(); it != d.end(); it++){
        sort((it->second).begin(), (it->second).end(), greater<ll>());
        l[it->first - wm] = (it->second).size();
        (it->second).insert((it->second).begin(), 0);
        for(int i=1; i<(it->second).size(); i++){
            (it->second)[i] += (it->second)[i-1];
        }
    }
    for(int i=0; i<4; i++){
        if(l[i]==0){
            d[wm+i] = {0};
        }
    }
    ll ans = 0;
    ll val = 0;
    for(int i0=0; i0<=l[0]; i0++){
        for(int i1=0; i1<=l[1]; i1++){
            for(int i2=0; i2<=l[2]; i2++){
                for(int i3=0; i3<=l[3]; i3++){
                    if(wm*(i0+i1+i2+i3)+i1+2*i2+3*i3<=w){
                        val = d[wm][i0]+d[wm+1][i1]+d[wm+2][i2]+d[wm+3][i3];
                        if(ans < val){
                            ans = val;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;

#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define INF 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
#define FOR(i,a,n) for(int i=a;i<n;i++) 
#define FORE(i,a,n) FOR(i,a,n+1)
#define Endl endl
#define eNdl endl
#define enDl endl
#define endL endl

int main()
{
	FOR(i,0,5)
	{
		ll a;
		cin>>a;
		if(a == 0)
		{
			cout<<i+1<<endl;
			return 0;
		}
	 } 
}


Measured memory_bytes: 3552