akhauriyash/Code-Regression huggingface dataset:
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static long MOD = 1000000007L;
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      long n = Long.parseLong(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      
      long answer = 0L;
      long[] sums = new long[(int)m+1];
      
      for(int k = m; k >= 1; k--){
         /*long num = ((exp(m/k,n)-sums[(int)k]+MOD)%MOD+MOD)%MOD;
         
         
         for(int j = 1; j*j <= k; j++){
            if(k%j == 0) sums[j] = (sums[j] + num + MOD)%MOD;
         }*/
         
         long num = exp((long)(m/k),n);
         
         for(int j = k*2; j <= m; j += k){
            num = num-sums[j];
            if(num < 0) num += MOD;
         }
         
         sums[k] = num;
         
         
         answer = (answer + k*num + MOD)%MOD;
      }
      
      
      out.println(answer);
      
      
      out.close();
   }
   
   public static long exp(long base, long power){
      if(power == 0) 
         return 1;
      if(power == 1) 
         return (base + MOD) % MOD;
      long ans = exp(base,power/2);
      ans = (ans*ans + MOD) % MOD;
      if(power%2 == 1) ans = (ans*base + MOD) % MOD;
      return (ans + MOD) % MOD;
   }
   
      
}

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

int main(){
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	
	sort(a.rbegin(), a.rend());
	
	ll ans = 0;
	for(int i = 1; i < n; ++i){
		ans += a[i / 2];
	}
	
	cout << ans << endl;
	return 0;
}



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

const int MOD = 2019;
string s;
int as[202020];
ll cnt[2222];

int main()
{
    cin >> s;
    int n = s.size();
    int p = 1;
    for(int i = n - 1; i >= 0; i--)
    {
        as[i] = (as[i + 1] + (p * (s[i] - '0'))) % MOD;
        p = (p * 10) % MOD;
    }


    rep(i, n)
    {
        cnt[as[i]]++;
    }
    
    ll sum = 0;
    rep(i, MOD)
    {
        sum += (cnt[i] * (cnt[i] - 1)) / 2;
    }
    sum += cnt[0];

    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 4564
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int k, n;
    cin >> k >> n;
    vec a(n);
    rep(i, n) cin >> a[i];

    sort(all(a));

    lint res = INF;

    rep(i, n) {
        lint d;
        if (i == n-1) {
            d = min(abs(a[i] - a[0]), k - abs(a[i] - a[0]));
        }
        else {
            d = min(abs(a[i] - a[i+1]), k - abs(a[i] - a[i+1]));
        }
        res = min(res, k - d);
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

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

Measured memory_bytes: 1152
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n; cin>>n;
    vector<int>a;
    rep(i,n){
      int b; cin>>b;
      a.push_back(b);
    }

    sort(a.begin(), a.end()); // 整列
    a.erase(unique(a.begin(), a.end()), a.end()); // 隣接する要素を削除

    if(n == a.size()) cout << "YES" << ln;
    else cout << "NO" << ln;

    return 0;
}



Measured memory_bytes: 1400
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let h: Vec<i32> = (0..n).map(|_| input()).collect();

    let mut ok = true;
    let mut hh = h[0];
    for i in 1..n {
        if h[i] + 1 < hh {
            ok = false;
            break;
        }
        hh = std::cmp::max(hh, h[i]);
    }
    println!("{}", if ok { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,h,w,a=0;cin>>n>>h>>w;
  for(int i=0;i<n;i++){
    int H,W;
    cin>>H>>W;
    if(H>=h&&W>=w)a++;
  }
  cout<<a<<endl;
}

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

int main(){
    long long N, A, B;
    cin >> N >> A >> B;
    if((B - A)%2 == 0){
        cout << (B - A)/2 << endl;
    }
    else{
        cout << min((2*N-A -B +1)/2, (A + B - 1)/2) << endl;
    }
}

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

int main() {
  int N, K, h, ans = 0;
  cin >> N >> K;
  
  for (int i = 0; i < N; i++) {
    cin >> h;
    if (h >= K) ans += 1;
  }
  
  cout << ans << endl;;
}

Measured memory_bytes: 3552
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            int n = Integer.parseInt(sc.nextLine());
            int[] a = Stream.of(sc.nextLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int q = Integer.parseInt(sc.nextLine());
            int[] ms = Stream.of(sc.nextLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            if (n != a.length || q != ms.length) {
                System.out.println("Conditions is invalid.");
                return;
            }
            HashMap<Integer, HashMap<Integer, Boolean>> dp = new HashMap<>();
            for (int target : ms) {
                if (hasCombination(target, a, 0, dp)) {
                    System.out.println("yes");
                } else {
                    System.out.println("no");
                }
            }
        } catch (NoSuchElementException
                | NumberFormatException e) {
            System.out.println(e);
        }
    }

    private static boolean hasCombination(
            int target,
            int[] elements,
            int i,
            HashMap<Integer, HashMap<Integer, Boolean>> dp
    ) {
        HashMap<Integer, Boolean> m = dp.get(i);
        Boolean a;
        if (m != null && (a = m.get(target)) != null) {
            return a;
        }

        if (m == null) {
            m = new HashMap<>();
            dp.put(i, m);
        }
        if (target == 0) {
            m.put(target, Boolean.TRUE);
        } else if (elements.length <= i) {
            m.put(target, Boolean.FALSE);
        } else if (hasCombination(target, elements, i + 1, dp)) {
            m.put(target, Boolean.TRUE);
        } else if (hasCombination(target - elements[i], elements, i + 1, dp)) {
            m.put(target, Boolean.TRUE);
        } else {
            m.put(target, Boolean.FALSE);
        }
        dp.put(i, m);

        return dp.get(i).get(target);
    }
}



Measured memory_bytes: 39684
import java.util.Scanner;

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

		int n = 0;
		for (int i = 0; i < 3; i++) {
			if (s.charAt(i) == 'o')
				n++;
		}
		System.out.print(700 + 100 * n);
	}
}

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

int a[50];
ll dp[51][2];
int main() {
	int n, p; scanf("%d%d", &n, &p);
	rep(i, n)scanf("%d", &a[i]), a[i] %= 2;
	dp[0][0] = 1;
	rep(i, n)rep(j, 2) {
		dp[i + 1][j] += dp[i][j];
		dp[i + 1][j^a[i]] += dp[i][j];
	}
	printf("%lld\n", dp[n][p]);
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	A := make([]int, N)
	sum := 0
	for i := range A {
		fmt.Scan(&A[i])
		sum += A[i]
	}
	res := 0
	for i := range A {
		res += A[i] * (sum - A[i])
	}
	fmt.Println(res / 2)
}



Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <array>
int main() {
	std::array<int, 100001> arr{ 0 };
	int n;
	std::cin >> n;
	int arg;
	for (auto i = 0; i < n; ++i) {
		std::cin >> arg;
		++arr[arg];
	}
	int sum = 1;
	for (const auto &a : arr) {
		if (a > 1) {
			sum += a - 1;
		}
	}
	std::cout << n - sum / 2 * 2 << std::endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int[] a = new int[N];
            for (int i = 0; i < a.length; i++) {
                a[i] = in.nextInt();
            }

            int count = 0;
            for (int i = 0; i < a.length; i++) {
                while (a[i] % 2 == 0) {
                    a[i] /= 2;
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}


Measured memory_bytes: 34272
#include <cstdio>
#include <cstring>
#include<iostream>

using namespace std;


char s[100001];
long int k = 0;
int n = 0;
int main(void) {
	

	

	cin >> s;
	cin >> k;


	int Len = strlen(s);

	for (int i = 0; i < Len-1; i++) {
		if (s[i] != 'a') {
			//aにするのに必要な数
			n = ('z' - s[i]) + 1;
			if (k - n >= 0) {
				k -= n;
				s[i] = 'a';
			}
		}
	}	
	if (k != 0) {
	
		s[Len-1] = 'a'+((s[Len - 1]-'a')+k)%26;
	}
	cout << s;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using plint = pair<lint, lint>;
constexpr lint MOD = 1000000007;

#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)

int N;
lint K;
vector<lint> A;

int countk(lint s, lint l)
{
    int ans = 0;
    for (int d = 62; d >= 0; d--)
    {
        ans += ((l >> d) & 1);
        if (((s >> d) & 1) != ((l >> d) & 1)) break;
    }
    return ans;
}

lint calc(vector<plint> x)
{
    sort(x.begin(), x.end());
    lint ans = 0;
    lint head = -1;
    for (auto v : x)
    {
        if (head < v.first) head = v.first - 1;
        if (head < v.second) ans += (v.second - head);
        head = max(head, v.second);
    }
    return ans;
}

int main()
{
    cin >> N >> K;
    A.resize(N);
    REP(i, N) cin >> A[i];

    map<vector<lint>, vector<plint>> m;
    vector<plint> B(N);

    REP(d, 62)
    {
        REP(i, N) B[i] = plint(A[i] & ((1LL << d) - 1), A[i] >> d);
        sort(B.begin(), B.end());
        REP(i, N) if (!(i && B[i].first == B[i-1].first))
        {
            vector<lint> C(N);
            REP(j, N) C[j] = B[j].second - (j<i ? 1 : 0);
            lint min_ = *min_element(C.begin(), C.end());
            if (min_ < 0) continue;
            REP(j, N) C[j] -= min_;
            sort(C.begin(), C.end());

            lint dd = 0;
            if (i) dd = countk(B[i-1].first, B[i].first);
            if (dd + d <= K) m[C].push_back(plint(max(min_-K+dd+d, 0LL), min_));
        }
    }

    lint ans = 0;
    for (auto v : m) (ans += calc(v.second)) %= MOD;
    cout << ans << endl;
}

Measured memory_bytes: 16512
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
typedef long long ll;

string rotate(string S, int i){
    int sz = S.size();
    string ans = "";
    rep(j,sz){
		ans += S[(j+i)%sz];
    }
    return ans;
}

void Main()
{
	string S, T;
  	cin >> S >> T;
	rep(i,S.size()){
    	if(T == rotate(S,i)){
			cout << "Yes" << endl;
            return;
    	}
    }
    cout << "No" << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}




Measured memory_bytes: 256
s = input()
q = int(input())
for i in range(q):
    command = input().split()
    command[1] = int(command[1])
    command[2] = int(command[2])
    if command[0] == 'print':
        print(s[command[1]:command[2]+1])
    elif command[0] == 'reverse':
        s = s[command[1]:command[2]+1][::-1].join([s[:command[1]], s[command[2]+1:]])
    elif command[0] == 'replace':
        s = command[3].join([s[:command[1]], s[command[2]+1:]])

Measured memory_bytes: 7732
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = {}
for i in range(N - 1):
    for j in range(i + 1, N):
        dist = min(j - i, abs(i - X) + 1 + abs(j - Y))
        if dist not in D:
            D[dist] = 1
        else:
            D[dist] += 1
for i in range(1, N):
    if i in D:
        print(D[i])
    else:
        print(0)

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i) // マクロ
using namespace std;                          // stdの省略
using pii = pair<int, int>;                   // pairの略記
using ll = long long;                         // long longの略記

int main(void)
{

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a.at(i);
    }

    ll cnt = 0;
    int bf = -1;
    for (auto x : a)
    {
        if (bf>x) cnt += bf - x;
        else bf = x;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3988
//prepared by dumb
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define llu unsigned long long int
#define scll(x) scanf("%lld",&x)
#define scld(x) scanf("%lf",&x)
#define scull(x) scanf("%llu",&x)
#define scch(x) scanf(" %c",&x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define ppb() pop_back()
#define ppf() pop_front()
#define Pi acos(-1.0)
#define INF 1e18
#define ff first
#define ss second
#define mpr make_pair
ll  _xor(ll a,ll b){return a^b;}
ll _and(ll a,ll b){return a&b;}
ll _or(ll a,ll b){return a|b;}
ll _not(ll a){ return ~a;}
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
           #ifndef ONLINE_JUDGE 
         freopen("input.txt","r",stdin);
         freopen("output.txt","w",stdout);
         #endif
    ll b,c,d,e,f,g,h,i,j,k,l1,l2,l3,t,a,m,n,p,q,r,s,u,v,x,y,c1,c2,c3;

        //scll(t);
        //while(t--)
        //{
             scll(a);
             scll(b);
             scll(c);
             scll(d);
            if(ceil(c/(1.0*b))>ceil(a/(1.0*d)))
                cout<<"No";
            else
            	cout<<"Yes";
return 0;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 200010;

int n;
string s[1010];

void link(int a, int b, int level){
    if(level == 0) return;
    For(i, a+1, b) s[i][level-1] = '|';
}

int pl(int i){
    if(s[i][0] != '.') return 0;
    rep(j, s[i].size()){
        if(s[i][j] != '.'){
            s[i][j-1] = '+';
            return j;
        }
        else s[i][j] = ' ';
    }
}

int main(){
    while(scanf("%d", &n) && n){
        rep(i, n) cin >> s[i];
        stack<pii> st;
        rep(i, n){
            int level = pl(i);
            while(!st.empty() && st.top().se > level) st.pop();
            if(!st.empty() && st.top().se == level){
                link(st.top().fi, i, level);
                st.pop();
            }
            st.emplace(i, level);
        }
        rep(i, n) cout << s[i] << "\n";
    }
}


Measured memory_bytes: 3792
import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = Long.parseLong(sc.next());
        long K = Long.parseLong(sc.next());
        System.out.println(value(N,K));
    }

    public static long value(long N, long K) {
        if (N%K > K-(N%K)) {
            return K - (N%K);
        }

        else {
            return N%K;
        }
    }
}




Measured memory_bytes: 23636
import numpy as np
import sys

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

def f(x):
    if x%4 == 0:
        return x
    elif x%4 == 1:
        return x^(x-1)
    elif x%4 == 2:
        return x^1
    else:
        return x^(x-1)^1

print(f(A-1)^f(B))

Measured memory_bytes: 12488
def main():
	t, *grid = open(0)
	h, w = map(int, t.split())
	vis = [[False] * w for _ in range(h)]
	ans = 0
	for y in range(h):
		for x in range(w):
			if vis[y][x]:
				continue
			q = [(y, x, grid[y][x])]
			d = {"#": 0, ".": 0}
			while q:
				cy, cx, cc = q.pop(0)
				for ny, nx in ((cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)):
					if not (0 <= ny < h and 0 <= nx < w) or vis[ny][nx] or cc == grid[ny][nx]:
						continue
					nc = grid[ny][nx]
					d[nc] += 1
					vis[ny][nx] = True
					q.append((ny, nx, nc))
			ans += d["#"] * d["."]
	print(ans)

if __name__=="__main__":
	main()

Measured memory_bytes: 4468
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

/* problem_D */
int main(){
    string s;
    cin >> s;
    int q;
    cin >> q;
    int ti[q];
    int fi[q];
    string ci[q];
    int a=0;
    string s1;
    string s2;
    
    for (int i=0; i<q; i++){
        cin >> ti[i];
        if (ti[i]==1){
            if (a==0){
                a=1;
            }
            else{
                a=0;
            }
        }
        else{
            cin >> fi[i];
            cin >> ci[i];
            if (fi[i]==1 && a==0){
                s1 = ci[i] + s1;
            }
            else if (fi[i]==1 && a==1){
                s2 = s2 + ci[i];
            }
            else if (fi[i]==2 && a==0){
                s2 = s2 + ci[i];
            }
            else{
                s1 = ci[i] + s1;
            }
        }
    }
    s = s1 + s + s2;
    if (a==0){
        cout << s << endl;
    }
    else{
        reverse(s.begin(), s.end());
        cout << s << endl;
    }
}

Measured memory_bytes: 22204
#include<bits/stdc++.h>
#define D(x) cerr<<#x<<'='<<x<<'\n';
using namespace std;
typedef long long ll;
int main()
{
  	int n;
  	scanf("%d",&n);
  	for (int i=1;i<=n;i++)
  	{
  		int x;
		scanf("%d",&x);
		if (x&1)
			continue;
		if (x%3!=0 && x%5!=0)
		{
			printf("DENIED");
			return 0;
		}
	}
	printf("APPROVED");
	return 0;
}


Measured memory_bytes: 256
from sys import stdin
from heapq import heapify, heappop
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    q = [(x, i) for i, x in enumerate(dat)]
    q.sort()
    d = [0] * n
    ans = min(sum(dat[::2]), sum(dat[1::2]))
    s = 0
    for i in xrange(n):
        s += q[i][0]
        d[q[i][1]/2] |= 1 << (q[i][1] % 2)
    for i in xrange(n):
        p = s
        c = n - 1
        for j in xrange(2):
            if not (d[i] >> j & 1):
                p += dat[i*2+j]
                while q[c][1] / 2 == i:
                    c -= 1
                p -= q[c][0]
                c -= 1
        if ans > p:
            ans = p
    print ans
main()


Measured memory_bytes: 32232
#include <iostream>
#include <string>

int min(int a, int b, int c);

int main(){
    std::string str1;
    std::string str2;
    std::cin >> str1;
    std::cin >> str2;
    int size1 = str1.size();
    int size2 = str2.size();
    int dp[size1+1][size2+1];
    dp[0][0] = 0;
    for(int j=0;j<=size1;j++){
        dp[j][0] = j;
    }
    for(int j=0;j<=size2;j++){
        dp[0][j] = j;
    }

    for(int j=1;j<=size1;j++){
        for(int k=1;k<=size2;k++){
            if(str1[j-1]==str2[k-1]){
                dp[j][k] = min(dp[j-1][k-1], dp[j-1][k] + 1, dp[j][k-1] + 1);
            }else{
                dp[j][k] = min(dp[j-1][k] + 1,dp[j-1][k-1] + 1, dp[j][k-1] + 1);
            }
        }
    }

    std::cout << dp[size1][size2] << std::endl;
    return 0;
}

int min(int a, int b, int c){
    if(a>b){
        return b>c ? c : b;
    }else{
        return a>c ? c : a;
    }
}


Measured memory_bytes: 7116
#include <bits/stdc++.h>
 
using namespace std;
 
int diff(string a, string b) {
  int d = 0;
  for(int i = 0; i < (int)a.size(); i++) {
    if(a[i]!=b[i]) d++;
  }
  return d;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int n = s.size(), m = t.size();
  int ans = 2e9;
  for(int i = 0; i <= (n-m); i++) {
    string cur = s.substr(i, m);
    ans = min(ans, diff(cur, t));
  }
  cout << ans << '\n';
  return 0;
}

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

using namespace std;

const int INF = 1 << 30;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  queue<pair<int, int>> que;
  que.push(make_pair(0, 0));
  vector<int> dist(N, INF);
  dist[0] = 0;
  vector<int> to(N, INF);
  to[0] = 0;
  while (!que.empty()) {
    auto q = que.front();
    que.pop();
    int d = q.first, u = q.second;
    if (dist[u] < d) continue;
    for (int g : G[u]) {
      int v = g;
      if (chmin(dist[v], d + 1)) {
        to[v] = u;
        que.push(make_pair(dist[v], v));
      }
    }
  }
  if (*max_element(to.begin(), to.end()) == INF) {
    cout << "No" << '\n';
  } else {
    cout << "Yes" << '\n';
    for (int i = 1; i < N; i++) {
      cout << to[i] + 1 << '\n';
    }
  }
  return 0;
}


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

#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;

ll mod = 1e9 + 7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll inf = 1ll << 60;



int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(a * n, b);
    return 0;
} 

Measured memory_bytes: 256
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N,A,B;
	cin>>N>>A>>B;
	cout<< ((B-A)&1?"Borys":"Alice") << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 256
N=gets.to_i
C,S,F=(N-1).times.map{gets.split.map &:to_i}.transpose

d=S+[0]
(0...N-1).each do |i|
  (0..i).each do |j|
    d[j]=S[i] if d[j]<S[i]
    d[j]=S[i]+F[i]*((d[j]-S[i]+F[i]-1)/F[i]) if S[i]<d[j]
    d[j]+=C[i]
  end
end
puts d


Measured memory_bytes: 3836
import sys

s = list(input())

del s[len(s) - 1]

while s:
  if len(s) % 2 == 1:
    del s[len(s) - 1]
    continue
  
  flag = True
  for i in range(len(s) // 2):
    if s[i] != s[len(s) // 2 + i]:
      flag = False
      break

  if flag:
    print(len(s))
    sys.exit()
  else:
    del s[len(s) - 1]


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

signed main () {
    int n;
    cin >> n;
    vector < int > a(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a.begin(), a.end());
    vector < int > nxt(n + 1, 0);
    for (int i = 1; i <= n; ++i) 
        nxt[i] = int(prev(upper_bound(a.begin(), a.end(), 2 * a[i])) - a.begin());
    vector < int > head(n + 1, 0);
    for (int i = n; i; --i) {
        head[i] = nxt[i];
        if (nxt[i] != i)
            head[i] = head[nxt[i]];
    }
    vector < int64_t > pref(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i - 1] + a[i];
    int good = n;
    for (int i = 0; i <= n; ++i) {
        if (head[i] == n) {
            good = a[i];
            break;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += (2 * pref[head[i]] >= int64_t(good));
    cout << ans << '\n';
}


Measured memory_bytes: 2176
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;
 
int main(int argc, char *argv[])
{
    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    int min = MOD;
    for (int i = 0; i < N; i++) {
        if (min > a[i]) {
            min = a[i];
        }
    }

    int max = 0;
    for (int i = 0; i < N; i++) {
        if (max < a[i]) {
            max = a[i];
        }
    }

    std::cout << max - min << std::endl;
    return 0;
}

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

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	if(a==b && a!=c && b!=c) cout << "Yes";
	else if(b!=a && b==c && a!=c) cout << "Yes";
	else if(c==a && c!=b && a!=b) cout << "Yes";
	else cout << "No";
	return 0;
}

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

int main() {
	char[] digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
	
	string l1, l2;
	readln();
	while((l1 = readln(), l1.length)){
		bool overflow = false;
		
		l2 = readln();
		if(!l1.split.length || !l2.split.length) break;
		
		char[] a, b, c;
		for(int i=0; i<80; i++) c ~= '0';
		
		a = cast(char[]) l1.split("\n")[0];
		if(a.length > 80) overflow = true;
		a = c ~ a;
		a = a[$ - 80 .. $];
		
		b = cast(char[]) l2.split("\n")[0];
		if(b.length > 80) overflow = true;
		b = c ~ b;
		b = b[$ - 80 .. $];
		
		for(int i = 79; i >= 0; i--){
			int t = (c[i] - '0') + (a[i] - '0') + (b[i] - '0');
			if(t >= 10){
				if(i == 0) overflow = true, t = 0;
				else while(t >= 10) c[i-1] += 1, t -= 10;
				}
			c[i] = digits[t];
			}
		if(overflow) printf("overflow\n");
		else{
			int i;
			for(i = 0; i < 79; i++){
				if(c[i] != '0') break;
				}
			c = c[i .. $];
			write(c ~ '\n');
			}
		}
	return 0;
	}

Measured memory_bytes: 1112
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)

#define INF 		2000000007
#define MOD			1000000000

#define MAX 		300005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

//int dp[MAX];

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

	int cnt=0;
	REP(i,N)if(S[i]=='E')cnt++;

	if(S[0]=='E')cnt--;
	int minl=cnt;
	REPS(i,1,N){
		cnt = cnt + (S[i-1]=='W') - (S[i]=='E');
		minl = min(minl,cnt);
	}

	cout << minl << endl;

	return 0;
}

Measured memory_bytes: 900
import sys
input = sys.stdin.readline

S,K=input().split()
K=int(K)
mod=998244353

LEN=len(S)

ONES=[]
Z=0
for s in S:
    if s=="0":
        Z+=1
    else:
        ONES.append(Z)

if ONES==[]:
    print(1)
    sys.exit()

O=len(ONES)
Z=ONES[-1]

DP=[[0]*(O+1) for i in range(min(O,K)+1)]
DP[0][0]=1

# DP[i][j]で, i個石を動かし、j個石が残っているときの場合の数

from collections import Counter
C=Counter(ONES)

for numb in range(Z,-1,-1):
    #print(DP)
    c=C[numb]

    NDP=[[0]*(O+1) for i in range(min(O,K)+1)]

    for i in range(min(O,K)+1):        
        for j in range(O+1):
            if DP[i][j]==0:
                continue
            for oku in range(c+j+1):
                if i+max(0,oku-c)<=min(O,K) and 0<=c+j-oku<=O:
                    NDP[i+max(0,oku-c)][c+j-oku]+=DP[i][j]
    DP=NDP

ANS=0
for i in range(min(O,K)+1):
    ANS+=DP[i][0]

print(ANS%mod)


Measured memory_bytes: 177108
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    int n;
    cin >> n;
    vector<int> p(n);
    REP(i, n) cin >> p[i];
    sort(p.begin(), p.end());
    REP(i, n){
        if(i<n-1) ans += p[i];
        else ans += p[i] /2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    A,B=pin()
    ans=0 if (A<B*2) else A-B*2
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """12 4"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """20 15"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """20 30"""
        output = """0"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Measured memory_bytes: 51308
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N - 1; i++){
        int a;
        cin >> a;
        A[a - 1]++;
    }
    for(int a : A) cout << a << endl;
}


Measured memory_bytes: 4004
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {

//    	File file = new File("test.txt");
//    	Scanner sc = new Scanner(file);
    	Scanner sc = new Scanner(System.in);
    	String s = sc.nextLine();
    	sc.close();
    	s = s.replaceAll("hi", "");
    	if(s.equals("")){
    		System.out.println("Yes");
    	}else{
    		System.out.println("No");
    	}
    }
}

Measured memory_bytes: 21844
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, h[100000][3],dp[100001][3], res=0, i; cin>>n;
    for(i=0;i<n;i++) cin>>h[i][0]>>h[i][1]>>h[i][2]; //a,b,c
    //dp[i]:i日目の幸福度の総和
    for(i=0;i<n+1;i++){
        dp[i+1][0] = h[i][0]+max(dp[i][1],dp[i][2]);
        dp[i+1][1] = h[i][1]+max(dp[i][2],dp[i][0]);
        dp[i+1][2] = h[i][2]+max(dp[i][0],dp[i][1]);
    }
    for(i=0;i<3;i++) chmax(res,dp[n][i]);
    cout<<res<<endl;
}

Measured memory_bytes: 5868
from math import floor, ceil
N = int(input())
A = list(map(int, input().split()))
A = sorted([A[i]-(i+1) for i in range(N)])


if N % 2 == 1:
    X = A[N // 2]
    ans = 0
    for a in A:
        ans += abs(a - X)
    print(ans)
else:
    X = (A[N // 2] + A[N // 2 -1]) / 2
    X1 = ceil(X)
    X2 = floor(X)
    ans1, ans2 = 0, 0
    for a in A:
        ans1 += abs(a - X1)
        ans2 += abs(a - X2)

    print(int(min(ans1, ans2)))


Measured memory_bytes: 26612
import java.util.*;

class Main{

    void solve(){
	Scanner sc = new Scanner(System.in);

	while(true){

	    int w = sc.nextInt();
	    int h = sc.nextInt();
	    if(w==0 && h==0) break;

	    int[][] map = new int[h][w];
	    for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
		    map[i][j] = sc.nextInt();
		}
	    }

	    int[][] dp = new int[h][w];
	    for(int i=0; i<w; i++){
		if(map[0][i]==0) dp[0][i] = 1;
	    }

	    for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
		    if(map[i][j]==0){
			int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
			if(i-1>=0 && map[i-1][j]==0) n1 = dp[i-1][j];
			if(i-1>=0 && j-1>=0 && map[i-1][j-1]==0) n2 = dp[i-1][j-1];
			if(i-1>=0 && j+1<w && map[i-1][j+1]==0) n3 = dp[i-1][j+1];
			if(i-2>=0 && map[i-2][j]==2) n4 = dp[i-2][j];
			dp[i][j] += n1 + n2 + n3 + n4;
		    }else if(map[i][j]==2){
			int n1 = 0, n2 = 0;
			if(i-1>=0 && map[i-1][j]==0) n1 = dp[i-1][j];
			if(i-2>=0 && map[i-2][j]==2) n2 = dp[i-2][j];
			dp[i][j] = n1 + n2;
		    }
		}
	    }

	    int ans = 0;
	    for(int i=0; i<w; i++){
		if(map[h-1][i]!=1) ans += dp[h-1][i];
		if(h-2>=0 && map[h-2][i]==2) ans += dp[h-2][i];
	    }

	    System.out.println(ans);
	}
    }

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

Measured memory_bytes: 23468
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner s = new Scanner(System.in);
        int n = Integer.parseInt(s.next());
        List<Integer> d = new ArrayList<Integer>();
        for(int i = 0; i < n; i++)
        {
            int num = Integer.parseInt(s.next());
            d.add(num);
        }

        Set<Integer> set = new HashSet<Integer>();
        for(int num : d) set.add(num);

        System.out.println(set.size());
        s.close();
    }
}


Measured memory_bytes: 22100
n, m = map(int, input().split())
anslist = [0 for i in range(m)]
for i in range(n):
    ka = list(map(int, input().split()))
    del ka[0]
    for i in ka:
        anslist[i - 1] += 1

ans = 0
for i in anslist:
    if i == n:
        ans += 1
print(ans)

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

int N;

int main() {
    cin >> N;
    bool flag = false;
    int cnt = 0;
    for (int i = 1; i < N + 1; i++) {
        int a;
        cin >> a;
        if (a == i) {
            if (flag) {
                flag = false;
            } else {
                ++cnt;
                flag = true;
            }
        } else {
            flag = false;
        }
    }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include<numeric>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
  int n,r;
  cin >> n >> r;
  if(n >= 10){
    cout << r << endl;
  }
  else{
  	cout << r + 100*(10-n) << endl;
  }
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
dic = defaultdict(int)
cnt = 0
ans = 0
for i in range(m):
    i,j = input().split()
    if dic[i] != -1:
        if j == 'WA':
            dic[i] += 1
        elif j == 'AC':
            cnt += 1
            ans += dic[i]
            dic[i] = -1
print(cnt,ans)


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

T={}
for a in A:
    if a in T:
        T[a]+=1
    else:
        T[a]=1

U=0
for a in T:
    U+=T[a]-1
U=((U+1)//2)*2
print(N-U)


Measured memory_bytes: 98236
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 1000000007

int R[200010], T[200010];
vector<int> es(524288, INT32_MAX), os = es;
vector<int> G[200010];

int smin(bool V, int& s, int& t, int k = 1, int l = 0, int r = 262143) {
	if (t < l || r < s) {
		return INT32_MAX;
	}
	if (s <= l && r <= t) {
		if (V)return os[k];
		return es[k];
	}
	int lv = smin(V, s, t, k * 2, l, (l + r) / 2);
	int rv = smin(V, s, t, k * 2 + 1, (l + r) / 2 + 1, r);
	return min(lv, rv);
}

void segfy(vector<int>& V) {
	for (int i = 262143;i > 0;i--) {
		V[i] = min(V[i * 2], V[i * 2 + 1]);
	}
}

void ans(int s, int t, bool b, int c) {
	if (s > t)
		return;
	int lv = smin(b, s, t);
	int l = R[lv];
	int rv = smin(!b, l, t);
	int r = R[rv];

	G[c].push_back(lv);
	T[lv] = rv;
	T[rv] = lv;
	ans(s, l - 1, b, lv);
	ans(l + 1, r - 1, !b, lv);
	ans(r + 1, t, b, lv);
}

int main() {
	int N, p;
	cin >> N;
	for (int i = 1;i <= N;i++) {
		cin >> p;
		if (i & 1) {
			os[i + 262144] = p;
			es[i + 262144] = INT32_MAX;
		}
		else {
			es[i + 262144] = p;
			os[i + 262144] = INT32_MAX;
		}
		R[p] = i;
	}
	segfy(es);segfy(os);

	ans(1, N, 1, 0);

	priority_queue<int, vector<int>, greater<int>> Q;
	Q.push(0);
	while (!Q.empty()) {
		p = Q.top();
		if (p)cout << p << " " << T[p] << " ";
		Q.pop();
		for (int i : G[p]) {
			Q.push(i);
		}
	}
	cout << endl;
}

Measured memory_bytes: 25856
from bisect import bisect_left
import numpy as np

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

border = np.arange(399, 3200, 400)
cnt = np.zeros(len(border) + 1, dtype=np.int)
for i in a:
    cnt[bisect_left(border, i)] += 1

k = np.count_nonzero(cnt[:-1])
print(k, k + cnt[-1]) if k != 0 else print(1, cnt[-1])

Measured memory_bytes: 12332
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
using ll = long long;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
vector<bool> isprime(1e6,true);
int main(){
    ll x;
    cin>>x;
    isprime[0]=false;
    isprime[1]=false;
    for(ll i=2;pow(i,2)<=2*x; i++){
        if(isprime[i]){
            for(ll j=2; i*j<=2*x; j++) isprime[i*j]=false;
        }
    }
    rep(i,x+x){
        if(isprime[i]&&i>=x){
            cout<<i<<endl;
            return 0;
        }
    }
    
}


Measured memory_bytes: 384
n,m=map(int,input().split())
dp=[[0]*(m+1) for _ in range(n+1)]

for i in range(1,n+1):
    w,v=map(int,input().split())
    dp[i][w]=max(dp[i-1][w],v)
    for j in range(m+1):
        if dp[i-1][j]==0:
            continue
        if j+w<=m:
            dp[i][j+w]=max(dp[i][j+w],dp[i-1][j]+v)

        dp[i][j]=max(dp[i-1][j],dp[i][j])


print(max(dp[n]))


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

#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200001
#define LIMIT2 500001
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define ffor(i, a, b, c) for(i=(int)(a);i<=(int)(b);i+=(int)c)
#define rep(i, n) for(i=0;i<(int)n;i++)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define bit(n) (1LL<<(n))
#define median(a, b) (a+b)/2.0
ll swap(ll *a,ll *b){ll tmp;tmp=*a;*a=*b;*b=tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
ll sum(ll *a,ll n){if(n<=0){return 0;}else{return sum(a,n-1)+a[n-1];}}
ld avg(ll *a,ll n){if(n<=0){return 0;}else return (ld)sum(a,n)/n;};
ld ABS(ld a){if(a>=0){return a;}else{return -a;}}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int stack[LIMIT2];//stack[0]=count;
int queue[LIMIT2];//stack[0]=start,stack[1]=length;
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
//qsort(s,n,sizeof(s[0]),upchar);
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
//qsort(s,n,sizeof(s[0]),downchar);
int push(int n){
    if(stack[0]>=LIMIT2) return -1;
    stack[0]++;
    stack[stack[0]] = n;
    return 1;
}
int pop(){
    if(stack[0]<=0) return -1;
    stack[0]--;
    return stack[stack[0]+1];
}
int enqueue(int n){
    if(queue[0]+queue[1]>=LIMIT2) return -1;
    queue[queue[0]+queue[1]] = n;
    queue[1]++;
    return 1;
}
int dequeue(){
    int result;
    if(queue[1]<=0) return -1;
    result = queue[queue[0]];
    queue[0]++;
    queue[1]--;
    if(queue[1]==0){
        queue[0] = 2;//queue reset
    }else if(queue[1]==1){
        queue[2] = queue[queue[0]];//only oneth
        queue[0] = 2;
    }
    return result;
}
void initialize(){
    stack[0] = 0;//stack size
    queue[0] = 2;//queue start
    queue[1] = 0;//queue length
}

int main(void){
  initialize();
  int n,m,p,i,j;
  ll result=0,iMax=0;
  char s[LIMIT1][10];
  ll a[LIMIT1]={0},b[LIMIT1]={0},c[LIMIT1]={0};
  scanf("%d", &n);
  rep(i,n){
    scanf("%lld", &a[i]);
  }
  
  rep(i,n){
    b[a[i]]++;
  }
  iMax=0;
  for(i=1;i<=n;i++) iMax+=(b[i])*(b[i]-1)/2;
  
  rep(i,n){
    j=a[i];
    result = iMax - b[j]*(b[j]-1)/2 + (b[j]-1)*(b[j]-2)/2;
    printf("%lld\n", result);
  }
  
  return 0;
}



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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#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 FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 998244353;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

ll mpow(ll m, ll p){
  ll power = m;
  ll res = 1;
  while(p>0){
    if(p&1)
      res = res*power%MOD;
    power = (power*power)%MOD;
    p /= 2;
  }

  return res;
}

ll mod_inv(ll m){
  return mpow(m, MOD-2);
}

struct COM{
  vll fact, fact_inv;
  COM(ll n): fact(n+1,1), fact_inv(n+1,1){
    for(ll i=1; i<=n; i++)
      fact[i] = fact[i-1]*i%MOD;

    fact_inv[n] = mod_inv(fact[n]);
    for(ll i=n; i>=1; i--)
      fact_inv[i-1] = fact_inv[i]*i%MOD;
  }

  ll calc(ll n, ll k){
    if(k<0 || n<k)
      return 0;
    ll res = fact[n]*fact_inv[n-k]%MOD*fact_inv[k]%MOD;
    return res;
  }
};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n,m,k;
  cin>>n>>m>>k;
  COM com(n+2);

  ll ans=0;
  for(ll i=0; i<=k; i++){
    ll now=m*mpow(m-1,n-1-i)%MOD*com.calc(n-1,i);
    //cout<<now<<endl;
    ans=(ans+now)%MOD;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 6300
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [float("inf")]*n

#初期条件
dp[0] = 0

#漸化式
for i in range(1,n):
    for l in range(1,k+1):
        if i-l < 0:continue
        dp[i] = min(dp[i],dp[i-l] + abs(h[i-l]-h[i]))

print(dp[n-1])

Measured memory_bytes: 55392
n=int(input())
ac=0
wa=0
tle=0
re=0

for i in range(n):
    x=input()
    if x == 'AC':
        ac+=1
    elif x == 'WA':
        wa+=1
    elif x == 'TLE':
        tle+=1
    elif x == 'RE':
        re+=1

print('AC x '+str(ac))
print('WA x '+str(wa))
print('TLE x '+str(tle))
print('RE x '+str(re))


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

int main(){
  int a, b, c, d;
  cin >> a >> b;
  c = a * b;
  d = (a + b) *2;

  cout << c << " "<< d << endl;
  //cout << a << " * " << b << " = " <<  c << " (a +b)*2 "<< d <<  endl;
  return 0;
}

Measured memory_bytes: 1164
#include<stdio.h>
int main(){
  int n,m,i,j,a[100][100],b[100],c[100];
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      scanf("%d",&a[i][j]);
    }
  }
  for(i=0;i<m;i++){
    scanf("%d",&b[i]);
  }
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      c[i]+=a[i][j]*b[j];
    }
  }
  for(i=0;i<n;i++){
    printf("%d\n",c[i]);
  }
  return 0; 
}



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

using namespace std;

int N,M;
char A[55][55],B[55][55];

bool in(int a,int b){
  for(int i=a; i<a+M; i++){
    for(int j=b; j<b+M; j++){
      if(A[i][j]!=B[i-a][j-b]){
        return 0;
      }
    }
  }
  return 1;
}

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>M;

for(int i=0; i<N; i++){
  cin>>A[i];
}
for(int i=0; i<M; i++){
  cin>>B[i];
}

for(int i=0; i+M-1<N; i++){
  for(int j=0; j+M-1<N; j++){
    if(in(i,j)){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
}

cout<<"No"<<endl;

}



Measured memory_bytes: 256