akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"flag"
	"fmt"
	"os"
	"sort"
	"strconv"
	"testing"
)

/*-----------Main-----------*/

func main() {
	n := readI()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = readI()
		if a[i] == 0 {
			fmt.Println(0)
			return
		}
	}
	ans := 1
	for _, v := range a {
		if ans > 1e18/v {
			ans = -1
			break
		} else {
			ans *= v
		}
	}
	fmt.Println(ans)

}

/*-----------Utilities-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	testing.Init()
	if flag.Parse(); flag.Arg(0) == "debug" {
		debug()
	}
	const maxBuf = 200100
	var buf []byte = make([]byte, maxBuf)
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBuf)
}

func debug() {
	testFile, err := os.Open("./test/sample-3.in")
	if err != nil {
		fmt.Println("Error : There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

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

func readSs(a int) []string {
	b := make([]string, a)
	for i := 0; i < a; i++ {
		b[i] = readS()
	}
	return b
}

func readI() int {
	sc.Scan()
	r, _ := strconv.Atoi(sc.Text())
	return r
}

func readIs(a int) []int {
	b := make([]int, a)
	for i := 0; i < a; i++ {
		b[i] = readI()
	}
	return b
}

func readF() float64 {
	sc.Scan()
	r, _ := strconv.ParseFloat(sc.Text(), 64)
	return r
}

func readFs(a int) []float64 {
	b := make([]float64, a)
	for i := 0; i < a; i++ {
		b[i] = readF()
	}
	return b
}

func max(a []int) int {
	l := len(a)
	m := a[0]
	for i := 1; i < l; i++ {
		if a[i] > m {
			m = a[i]
		}
	}
	return m
}

func min(a []int) int {
	l := len(a)
	m := a[0]
	for i := 1; i < l; i++ {
		if a[i] < m {
			m = a[i]
		}
	}
	return m
}

func sortI(a []int) []int {
	sort.Ints(a)
	return a
}

func reverse(a []int) []int {
	l := len(a)
	r := make([]int, l)
	for i := 0; i < l; i++ {
		r[i] = a[l-i-1]
	}
	return r
}

func countI(a []int, b int) int {
	l := len(a)
	var c int
	for i := 0; i < l; i++ {
		if a[i] == b {
			c++
		}
	}
	return c
}


Measured memory_bytes: 5968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ln '\n';
int lim=1e6;
int inf=1e9+7;
ll solve(ll* dp,int n,int i,ll* h){
	if(dp[i]!=-1){
		return dp[i];
	}
	if(i==n-1){
		return 0;
	}else{
		if(i<n-2){
			ll tmp1=solve(dp,n,i+1,h);
			ll tmp2=solve(dp,n,i+2,h);
			ll ans=min((abs(h[i]-h[i+1])+tmp1),(abs(h[i]-h[i+2])+tmp2));
			dp[i]=ans;
			return ans;
		}else{
			ll ans=(abs(h[i]-h[i+1]));
			dp[i]=ans;
			return ans;
		}
	}
}
int main()
{	
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	ll h[n];
	for(int i=0;i<n;i++){
		cin>>h[i];
	}		
	ll dp[n];
	for(int i=0;i<n;i++){
		dp[i]=-1;
	}
	cout<<solve(dp,n,0,h)<<ln;
}

Measured memory_bytes: 9600
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = 
                new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int num = Integer.parseInt(line);
        System.out.println(num * num * num);
    }
}

Measured memory_bytes: 24224
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
    int x;
    int y;
}a[100005];
bool cmp(node a,node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    cin>>a[i].x>>a[i].y;
    sort(a,a+m,cmp);
    int t=100000;
    int sum=1;
    for(int i=0;i<m;i++)
    {
        t=min(t,a[i].y);
    }
    for(int i=0;i<m;i++)
    {
        if(a[i].x>=t)
        {
            t=a[i].y;
            sum++;
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 1024
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        while(true) {
            String testCase = sc.nextLine();

            if (testCase.equals("0 0 0")) {
                return;
            }
            String [] arrInput =  testCase.split(" ");
            System.out.println(maxNewTax(Integer.valueOf(arrInput[2]), Integer.valueOf(arrInput[0]), Integer.valueOf(arrInput[1])));
        }
    }

    public static int maxNewTax(int totalOldTax, int oldTax, int newTax) {
        int maxNewTax = 0;
        for (int valOldTax1 = 1; valOldTax1 < totalOldTax; valOldTax1++) {
            int valOldTax2 = totalOldTax - valOldTax1;

            int val1 = (int) Math.ceil(100 * (double) valOldTax1 / (100 + oldTax));
            if(valOldTax1 != calculateTax(val1, oldTax)) {
                val1 = (int) Math.floor(100 * (double) valOldTax1 / (100 + oldTax));
                if(valOldTax1 != calculateTax(val1, oldTax)) {
                    continue;
                }
            }


            int val2 = (int) Math.ceil(100 * (double) valOldTax2 / (100 + oldTax));
            if(valOldTax2 != calculateTax(val2, oldTax)) {
                val2 = (int) Math.floor(100 * (double) valOldTax2 / (100 + oldTax));
                if(valOldTax2 != calculateTax(val2, oldTax)) {
                    continue;
                }
            }


            int valNewTax = val1 * (100 + newTax)/100 + val2 * (100 + newTax)/100;
            maxNewTax = valNewTax > maxNewTax ? valNewTax : maxNewTax;
        }
        return maxNewTax;
    }

    public static int calculateTax(int val, int tax) {
        return val * (100 + tax) / 100;
    }
}


Measured memory_bytes: 27960
#include<stdio.h>
#include<math.h>
#define int long long
 
int min(int a,int b)
{
        if(a<b)
                return a;
        return b;
}
int main()
{ // dp array mein store kar ki n tak pahuchne mein ek pt se kitte paise lagenge
        int n;
        scanf("%lld",&n);
 
        int l=n+1;
        int h[l];
        int dp[l];
	int k;
	scanf("%lld",&k);
        for(int i=1;i<=n;i++)
        {scanf("%lld",&h[i]);}
        dp[1]=0;
        dp[2]=fabs(h[2]-h[1]);
	int mini=1e9+7;
	int minim=1e9+7;
	int minix=1e9+7;
	if (k>n)
	{
		for(int i=3;i<=n;i++)
		{
			  for(int j=1;j<i;j++)
                {
                 minix=min((fabs(h[i]-h[j])+dp[j]),minix);
                }
                dp[i]=minix;
                minix=1e9+7;
 
		}
		printf("%lld",dp[n]);
		return 0;
 
	}
	else
	{
	for(int i=3;i<=k;i++)
        {
		for(int j=1;j<i;j++)
		{
                 mini=min((fabs(h[i]-h[j])+dp[j]),mini);
		}
		dp[i]=mini;
		mini=1e9+7;
        }
	for(int i=k+1;i<=n;i++)
	{ 
		for(int j=i-k;j<i;j++)
		{
			minim=min((fabs(h[i]-h[j])+dp[j]),minim);
		}
		dp[i]=minim;
		minim=1e9+7;
	}
        printf("%lld",dp[n]);
	}
        return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;

int main(){
    ll n,m; cin >> n >> m;
    ll ans = n * (n-1) / 2;
    ans += m * (m-1) / 2;

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
	final public static int MOD = (int)1e9+7;
	public static long dp1[][];
	public static int arr[];
	public static long tot[];
    public static void main(String[] args) throws IOException{
    	FastScanner sc = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    	int n= sc.nextInt();
    	dp1 = new long[n][n];
    	tot = new long[n+1];
    	tot[0] = 0;
    	for(int i=0; i<n; i++) {
    		Arrays.fill(dp1[i], -1);
    	}
    	arr = new int[n];
    	for(int i=0; i<n; i++) {
    		arr[i] = sc.nextInt();
    		tot[i+1] = tot[i]  + arr[i];
    	}
    	long ans = go(0,n-1);
    	out.println(2*ans-(tot[n]));
    	out.close();
    }
    public static long go(int start, int end) {
    	if(start == end) {
    		return arr[start];
    	}
    	if(dp1[start][end]!=-1) return dp1[start][end];
    	dp1[start][end] = tot[end+1]-tot[start] - Math.min(go(start+1, end), go(start, end-1));
    	return dp1[start][end];
    	
    }
    public static class FastScanner {
    	BufferedReader br;
    	StringTokenizer st;

    	public FastScanner(String s) {
    		try {
    			br = new BufferedReader(new FileReader(s));
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		}
    	}

    	public FastScanner() {
    		br = new BufferedReader(new InputStreamReader(System.in));
    	}
    	
    	String nextToken() {
    		while (st == null || !st.hasMoreElements()) {
    			try {
    				st = new StringTokenizer(br.readLine());
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}

    	String nextLine() {
    		st = null;
    		try {
    			return br.readLine();
    		} catch (IOException e) {
    			e.printStackTrace();
    		}
    		return null;
    	}

    	int nextInt() {
    		return Integer.parseInt(nextToken());
    	}

    	long nextLong() {
    		return Long.parseLong(nextToken());
    	}

    	double nextDouble() {
    		return Double.parseDouble(nextToken());
    	}
    }
}


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

char s[110];

int main() {
	cin >> s + 1;
	int n = strlen(s + 1);
	bool ok = true;
	for (int i = 1; i <= n; i++) {
		ok = false;
		if (i & 1) {
			if (s[i] == 'R' || s[i] == 'U' || s[i] == 'D') continue;
		} else {
			if (s[i] == 'L' || s[i] == 'U' || s[i] == 'D') continue;
		}
		if (ok == false) return cout << "No", 0;
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>


using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;


const long long int mod = 1000000007;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 

long long int N,M,K,l[200030],r[200300],res=0;
string str;


int main()
{
    cout << fixed << setprecision(18);
    cin>>N;
    for(long long int i = 0; i < N; i++){
        cin>>l[i]>>r[i];
        res+=r[i]-l[i]+1;
    }
    cout<<res<<endl;
    
}    


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
  int n;
  int a[100005],b[100005],c[100005];
  int dp[4][100005];
  int ans;
  
  cin >> n;

  for(int i=0; i<n; i++) cin >> a[i] >> b[i] >> c[i];

  dp[1][0] = a[0];
  dp[2][0] = b[0];
  dp[3][0] = c[0];

  for(int i=1; i<n; i++){
    dp[1][i] = max(dp[2][i-1], dp[3][i-1]) + a[i];
    dp[2][i] = max(dp[1][i-1], dp[3][i-1]) + b[i];
    dp[3][i] = max(dp[1][i-1], dp[2][i-1]) + c[i];
  }

  ans = max(dp[1][n-1], dp[2][n-1]);
  cout << max(ans, dp[3][n-1]) << endl;

  return 0;

}


Measured memory_bytes: 2944
using System;

namespace ColorfulHats
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String input = Console.ReadLine();
            String[] splitted = input.Split(' ');
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(splitted[i]);
            }

            long result = 1;
            int[] number = new int[] { 0, 0, 0 };
            for (int i = 0; i < N; i++)
            {
                int count = 0;
                for(int j = 0; j < 3; j++)
                {
                    if (number[j] == A[i])
                    {
                        count++;
                    }
                }
                result = ((result % 1000000007) * count)% 1000000007;
                for(int j = 0; j < 3; j++)
                {
                    if (number[j] == A[i])
                    {
                        number[j]++;
                        break;
                    }
                }
            }
            Console.WriteLine(result);
        }
    }
}


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

using namespace std;

using ll = long long;
using T = tuple<string, int, int>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<T> v;
    for (int i = 0; i < n; i++) {
        string s;
        int p;
        cin >> s >> p;
        v.emplace_back(s, -p, i + 1);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        cout << get<2>(v[i]) << endl;
    }
    return 0;
}

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

int main(void){
    int N;
    int a[200000];
    int r[210000];
    vector<int> result;

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

    for(int i=N-1; i>=0; --i){
        int sum_multiples=0;

        for(int j=2; j*(i+1)-1<N; ++j){
            sum_multiples += r[j*(i+1)-1];
        }
        
        if(sum_multiples%2 != a[i]){
            r[i] = 1;
            result.insert(result.begin(),i+1);
        }
    }

    if(result.size()==0){
        cout << 0 << endl;
        return 0;
    }
    
    cout << result.size() << endl;
    for(auto i=result.begin(); i!=result.end(); ++i){
        cout << *i;
        if(i+1!=result.end())
            cout << " ";
        else
            cout << endl;
    }
    return 0;
}


Measured memory_bytes: 2936
S = input()
T = input()

ans = 'UNRESTORABLE'
memo = -1

for i in range(len(S) - len(T) + 1):
    cnt = 0
    for j in range(len(T)):
        if S[i+j] == T[j] or S[i+j] == '?':
            cnt += 1
        else:
            break
        if cnt == len(T):
            ans = T
            memo = i


if ans == 'UNRESTORABLE':
    print(ans)
else:
    ans = ''
    ans = S.replace('?','a')
    print(ans[:memo]+T+ans[memo+len(T):])


Measured memory_bytes: 3064
n, m = gets.split.map(&:to_i)
ds = m.times.map{gets.split.map(&:to_i)}.sort_by{|a,b|b}
res = 0
front = 1
ds.each{|a, b|
    if a >= front
        res += 1
        front = b
    end
}
p res

Measured memory_bytes: 13560
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

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

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;

int N;
char B[1005][1005];

void putDomino(vector<PII> D) {
  vector<bool> taken(10);
  for (auto p: D) {
    if (p.st > 0 && B[p.st-1][p.nd] != '.') taken[B[p.st-1][p.nd]-'a'] = true;
    if (p.st < N-1 && B[p.st+1][p.nd] != '.') taken[B[p.st+1][p.nd]-'a'] = true;
    if (p.nd > 0 && B[p.st][p.nd-1] != '.') taken[B[p.st][p.nd-1]-'a'] = true;
    if (p.nd < N-1 && B[p.st][p.nd+1] != '.') taken[B[p.st][p.nd+1]-'a'] = true;
  }
  int k = 0;
  while (taken[k]) ++k;
  for (auto p: D) {
    assert(B[p.st][p.nd] == '.');
    B[p.st][p.nd] = 'a' + k;
  }
}

void putHorizontal(int r, int c) {
  putDomino({{r,c},{r,c+1}});
}

void putVertical(int r, int c) {
  putDomino({{r,c},{r+1,c}});
}

void put3a(int r, int c) {
  putHorizontal(r,c);
  putVertical(r+1,c+2);
}

void put3b(int r, int c) {
  putHorizontal(r,c);
  putVertical(r,c+2);
  putHorizontal(r+2,c+1);
  putVertical(r+1,c);
}

void put2Vertical(int r, int c) {
  putVertical(r,c);
  putVertical(r,c+1);
}

void put2Horizontal(int r, int c) {
  putHorizontal(r,c);
  putHorizontal(r+1,c);
}

void put4(int r, int c) {
  put2Vertical(r,c);
  put2Horizontal(r+2,c);
  put2Horizontal(r,c+2);
  put2Vertical(r+2,c+2);
}

void put5(int r, int c) {
  putHorizontal(r,c);
  putHorizontal(r,c+2);
  putVertical(r,c+4);
  putVertical(r+2,c+4);
  putHorizontal(r+4,c+3);
  putHorizontal(r+4,c+1);
  putVertical(r+3,c);
  putVertical(r+1,c);
  put3a(r+1,c+1);
}

void put6(int r, int c) {
  put3a(r,c);
  put3b(r+3,c);
  put3b(r,c+3);
  put3a(r+3,c+3);
}

void put7(int r, int c) {
  putHorizontal(r,c+1);
  putHorizontal(r,c+3);
  putHorizontal(r,c+5);
  putVertical(r+1,c);
  putVertical(r+3,c);
  putVertical(r+5,c);
  put3a(r+1,c+1);
  put3a(r+4,c+1);
  put3a(r+4,c+4);
  put3a(r+1,c+4);
}

void go(int N) {
  if (N == 3) {
    put3a(0,0);
  } else if (N == 4) {
    put4(0,0);
  } else if (N == 5) {
    put5(0,0);
  } else if (N == 6) {
    put6(0,0);
  } else if (N == 7) {
    put7(0,0);
  } else {
    put4(N-4,N-4);
    go(N-4);
  }
}

int main() {
  // ios_base::sync_with_stdio(0);


  scanf("%d", &N);
  REP(i,N)REP(j,N) B[i][j] = '.';
  if (N < 3) {
    printf("-1\n");
    return 0;
  }
  go(N);
  REP(i,N) printf("%s\n", B[i]);
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ri register int
const int N=1505;
int a[N][N],f[N][N],l[N][N],r[N][N];
char s[N];
/* 
f[i][j] (i,j) 能走到的位置的权值和
l[i][j][k]/r[i][j][k] 表示 (i,j) 可以到达的第 k 行最左/右的位置 ，第一维省略
不能走到的点贡献相当于已经清零，因为 (i+1,j) (i,j+1) 共同能走到的点的递增序列里面不会出现这些位置，
且没有被计算到其左上的点的贡献中去 
*/
int main(){
//	freopen("cell.in","r",stdin);
//	freopen("cell.out","w",stdout);
	ri n,i,j,k,now;
	register long long ans;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%s",s+1);
		for(j=1;j<=n;++j)
			a[i][j]=s[j]=='#'?0:s[j]-'0';
	}
	ans=0;
	for(i=n;i;--i)
		for(j=n;j;--j){
			if(a[i][j]==0){
				memset(l[j]+i,127,sizeof(int)*(n-i+1));
				memset(r[j]+i,128,sizeof(int)*(n-i+1));
				continue;
			}
			if(a[i+1][j]==0&&a[i][j+1]==0)
				l[j][i]=r[j][i]=j;
			else if(a[i+1][j]==0)
				memcpy(l[j]+i,l[j+1]+i,sizeof(int)*(n-i+1)),
				memcpy(r[j]+i,r[j+1]+i,sizeof(int)*(n-i+1)),
				l[j][i]=j,
				f[i][j]=f[i][j+1];
			else if(a[i][j+1]==0)
				l[j][i]=r[j][i]=j,
				f[i][j]=f[i+1][j];
			else{
				f[i][j]=f[i][j+1]+f[i+1][j];
				l[j][i]=j;r[j][i]=r[j+1][i];
				now=0;
				for(k=i+1;k<=n;++k){
					if(r[j][k]>=l[j+1][k]&&l[j+1][k]>now)
					//	printf("sub %d %d %d %d\n",i,j,k,l[j+1][k]),
						f[i][j]-=f[k][l[j+1][k]];
					now=max(now,r[j][k]);
					l[j][k]=min(l[j][k],l[j+1][k]);
					r[j][k]=max(r[j][k],r[j+1][k]);
				}
			}
			ans+=a[i][j]*f[i][j];
		//	printf("f %d %d %d\n",i,j,f[i][j]);
			f[i][j]+=a[i][j];
		//	printf("check (%d,%d)\n",i,j);
		//	for(k=i;k<=n;++k)
		//		printf("%d %d %d\n",k,l[j][k],r[j][k]);
		}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 39104
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

vector<ll> lis(vector<ll> &a){
	ll n=a.size();
	vector<ll> L;
	L.push_back(a[0]);
	ll length=1;
	for(ll i=1;i<n;i++){
		if(L[length-1]<=a[i]){
			L.push_back(a[i]);
			length++;
		}else{
			//auto it=lower_bound(L.begin(), L.end(), a[i]);
			auto it=upper_bound(L.begin(), L.end(), a[i]);
			*it=a[i];
			debug(L);
		}
	}
	debug(length);
	return L;
}

signed main() {
	//ABC134E
	ll N;
	vector<ll> a;
	cin>>N;
	a.assign(N,0);
	rep(i, N) {
		cin>>a[i];
	}

	reverse(a.begin(),a.end());
	vector<ll> l;
	l=lis(a);
	p(l.size());
	debug(l);

	return 0;
}


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

int main(void){
	while(1){
		long q;
	
		scanf("%ld", &q);
		if(q==-1) break;
		
		double x = q/2.0;
		
		//printf("x^3=%lf, q=%lf", x*x*x, (double)q);
		
		//printf("%lf\n", fabs(x*x*x-q));
		
		while(fabs(x*x*x - q) >= q*0.00001){
			x = x - (x*x*x-q)/(3*x*x);
			//printf("now: %lf\n",x);
		}	
	
		printf("%lf\n", x);
	}

	return 0;
}

Measured memory_bytes: 632
L = int(input())
node = 0
for i in range(21):
    if L < 2**i:
        L2 = 2**(i-1)
        N = i
        node = i - 1
        break

l = L - L2

L_reg = L2
L_tmp = L2
L_new = L2
L_bai = 1

a = []
b = []

def make_arr(init, N, a, b):
    global L_reg
    global L_tmp  # 各再帰計算時の値
    global L_new  # 単純なループ用
    global L_bai

    L_new = L_reg

    if [init, N] in a:
        # L_tmp = L_new
        L_tmp = L_new - L_bai
        L_bai *= 2
        # L_new += 1
        make_arr(init+1, N, a, b)
        a.remove([init, N])
        b.remove(max(b))
    else:
        a.append([init, N])
        b.append(L_new)
        L_reg += 1
        L_bai = 1


for i in range(l):
    make_arr(1,N,a,b)

for i in range(len(a)):
    a[i].append(b[i])

arr_0 = []
arr_2 = []

for i in range(node):
    arr_0.append([i + 1, i + 2, 0])
    arr_2.append([i + 1, i + 2, 2**i])

print(node+1,len(arr_0)+len(arr_2)+len(a))
for i in arr_0:
    print(i[0], i[1], i[2])
for i in arr_2:
    print(i[0], i[1], i[2])
for i in a:
    print(i[0], i[1], i[2])

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

typedef long long lli;
const int MAXH = 21;
const int MAXW = 21;
const lli mod = 100000LL;
const string C = "JOI";

int H, W;
char G[MAXH][MAXW];
lli dp[2][1<<MAXW];

int main() {
  lli all = 1;
  cin >> H >> W;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      cin >> G[i][j];
      if(G[i][j] == '?') {
        all = (all * 3) % mod;
      }
    }
  }
  dp[0][0] = 1;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      bool p = (i*W+j)%2;
      fill(dp[!p], dp[!p] + (1<<MAXW), 0LL);
      for(int b = 0; b < (1<<W); ++b) {
        for(int k = 0; k < 3; ++k) {
          if(G[i][j] == '?' || G[i][j] == C[k]) {
            int nb = b & ~(1<<j);
            if(C[k] == 'J') {
              nb &= ~(1<<(j-1));
              if(j+1 != W) nb |= (1<<j);
              dp[!p][nb] = (dp[!p][nb] + dp[p][b]) % mod;
            } else if(C[k] == 'O') {
              dp[!p][nb] = (dp[!p][nb] + dp[p][b]) % mod;
            } else if(C[k] == 'I') {
              if(!(b & (1<<j))) {
                nb &= ~(1<<(j-1));
                dp[!p][nb] = (dp[!p][nb] + dp[p][b]) % mod;
              }
            }
          }
        }
      }
    }
  }
  lli sum = 0;
  for(int b = 0; b < (1<<W); ++b) {
    sum = (sum + dp[H*W%2][b]) % mod;
  }
  cout << (all - sum + mod) % mod << endl;
  return 0;
}

Measured memory_bytes: 33964
package main

// Solution for https://atcoder.jp/contests/aising2020/tasks/aising2020_c

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

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var n int
	con.Scan(&n)
	a := make([]int, n+1)
	for x := 1; x <= n; x++ {
		p := x * x
		if p > n {
			break
		}
		for y := 1; y <= n; y++ {
			q := p + y*y + x*y
			if q > n {
				break
			}
			for z := 1; z <= n; z++ {
				r := q + z*z + y*z + z*x
				if r > n {
					break
				}
				a[r]++
			}
		}
	}
	for i := 1; i <= n; i++ {
		con.Println(a[i])
	}
	return nil
}


Measured memory_bytes: 1996
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,d,div,rem;
  cin>>n>>d;
  int val=(d*2)+1;
  div=n/val;
  rem=n%val;
  if(rem!=0){
    div=div+1;
  }
  else{
    div=div;}
  cout<<div;
  return 0;
}
  
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
using namespace std;

const int maxn = 100001;
const int maxe = 20;
int n,m,a[maxn],c=0,k,pa[maxn];
double f=0;
int st[maxn][maxe];

void build(int n){
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int a, int b){
    int k = 31- __builtin_clz(b-a+1);
    return min(st[a][k], st[b-(1<<k)+1][k]);
}

int find(int i)
{
    if(pa[i]==i)return i;
    return pa[i]=find(pa[i]);
}

int bs(int l,int r,int x)
{
    while(l!=r)
    {
        int mi=(l+r)/2;
        if(a[mi]>x)r=mi;
        else l=mi+1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>k;
    a[k]=i;
    }
    for(int i=1;i<n;i++){
    cout<<a[i]<<' ';
    }
    cout<<a[n];
}


Measured memory_bytes: 1280
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll=long long;

int main()
{
	int m1,d1,m2,d2;
	cin>>m1>>d1>>m2>>d2;
	cout<<(d2==1?1:0)<<endl;
	return 0;
}


Measured memory_bytes: 256
#-*- coding:utf-8 -*-

import bisect

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [0]*M
for i in range(M):
    BC[i] = [int(n) for n in  input().split()]

A.sort()    # 昇順ソートO(NlogN)
BC.sort(key=(lambda x: x[1]), reverse=True)   # Ciの値で降順ソート

st = 0 # 編集開始位置
for i in range(M):  # O(MlogN)
    b, c = BC[i]
    idx = bisect.bisect_left(A, c, st)  # A全体でのidxを返す
    edit = idx - st # 編集個数
    edit = min(b, edit)
    for j in range(edit):
        A[st+j] = c
    st += edit

print(sum(A))

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

int gcd(int n, int m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

int main()
{
    int n;
    cin >> n;
    int a[100005];
    for(int i = 0; i < n; i++) cin >> a[i];
    if(n == 1){
        cout << "Second" << endl;
        return 0;
    }
    if(n == 2){
        if(a[0] % 2 == a[1] % 2) cout << "Second" << endl;
        else cout << "First" << endl;
        return 0;
    }
    bool first = true;
    while(true){
        int m = 2;
        int l = 0;
        int c = 0;
        for(int i = 0; i < n; i++){
            m = min(m, a[i]);
            if(a[i] % 2) c++;
            else l = 1 - l;
        }
        if(l == 1){
            if(first) cout << "First" << endl;
            else cout << "Second" << endl;
            return 0;
        }
        else if(c > 1 || m == 1){
            if(first) cout << "Second" << endl;
            else cout << "First" << endl;
            return 0;
        }
        else{
            for(int i = 0; i < n; i++) a[i] = a[i] / 2 * 2;
            int g = 0;
            for(int i = 0; i < n; i++) g = gcd(g, a[i]);
            for(int i = 0; i < n; i++) a[i] /= g;
        }
        first = !first;
    }
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
from collections import *

Q, H, S, D = map(int, input().split())
N = int(input())
S = min(S, 4*Q, 2*H)
D = min(D, 8*Q, 4*H, 2*S)
print(N//2*D+N%2*S)

Measured memory_bytes: 38384
#include <iostream>
using namespace std;
int main(void){
   int K;
   cin>>K;
   string S;
   cin>>S;
   if(K>=S.length()){
       cout<<S<<endl;
   }
   else {
       for(int i=0;i<K;i++){
           cout<<S[i];
       }
       cout<<"..."<<endl;
   }
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"

using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lin "\n"
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(0)

void solve() {
    string a, b, c;
    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2];
}

int main() {
    fast_io;
    int t = 1;
//    cin >> t;
    int c = 1;
    while (t--) {
//        printf("Case %lld: ",c);
//        cout<<"Case "<<c<<": ";
        solve();
        c++;
    }
}

Measured memory_bytes: 3524
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	a := getNextFloat64(scanner)
	b := getNextFloat64(scanner)
	x := getNextFloat64(scanner)

	h := x / a / a
	var sq, ans float64
	l := 0.0
	r := 90.0
	diff := 1e-9
	if (b-h)*2 <= b {
		sq = math.Sqrt(a*a + (b-h)*(b-h)*4.0)

		for l+diff < r {
			m := (l + r) / 2.0
			if sq*math.Cos(m*math.Pi/180.0) < a {
				r = m
				continue
			}
			l = m
		}
		ans = l
	} else {
		h = 2 * x / a / b
		sq = math.Sqrt(b*b + h*h)
		for l+diff < r {
			m := (l + r) / 2.0
			if sq*math.Sin(m*math.Pi/180.0) < b {
				l = m
				continue
			}
			r = m
		}
		ans = l
	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}

signed main()
{
  int X, A;
  cin >> X >> A;

  int ans = 10;
  if (X < A) ans = 0;

  cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            int h = int.Parse(Console.ReadLine());
            Console.WriteLine((a + b) * h / 2);
        }
    }
}


Measured memory_bytes: 2648
#include<stdio.h>
#include<stdlib.h> 
struct Node{ int key; 
struct Node *right,*left,*parent; 
    }; 
    struct Node *root,*NIL;
    
   struct Node * getminimum(struct Node * x){
  while(x->left!=NIL){
    x=x->left;
      }
  return x;

}
   
  struct Node * treeSuccessor(struct Node * x){
  
  if(x->right!=NIL)
    return getminimum(x->right);
struct  Node *y = x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
  

}

   
    
    struct Node * find(struct Node *u,int k){ 
    while(u != NIL && k != u->key){ 
        
        if(k<u->key)u=u->left; 
    else u = u->right; 
        
    } 
    return u;
    } 
    
    void insert(int k){ 
        struct Node *y = NIL; 
        struct Node *x = root; 
        struct Node *z; 
        
        z = (struct Node *)malloc(sizeof(struct Node)); 
        z->key = k; z->left = NIL; 
        z->right = NIL; 
        
        while(x != NIL){ 
            y = x; 
            if(z->key < x->key){ x = x->left;
            }
            else{ x = x->right; 
                
            } 
            
        } 
        z->parent = y;
        
        
        if(y == NIL)root = z; 
            
        
        else{ 
            if(z->key < y->key){ 
                y->left = z; 
                
            }
            
            else  y->right = z; 
                
            
            } 
        
    } 
    
    void delete(struct Node *z){
 struct Node * y; // 削除するノード
 struct Node * x; //yの子ノード
  
  if(z->left==NIL || z->right==NIL)
    y=z;
  else y=treeSuccessor(z);
  
  if(y->left!=NIL)
    x=y->left;
  else
    x=y->right;
    
  if(x!=NIL)
    x->parent=y->parent;
    
  if(y->parent==NIL)
    root=x;
  else if(y==y->parent->left)
    y->parent->left=x;
  else
    y->parent->right=x;
  if(y!=z) z->key=y->key;
  
  free(y);

    }
    
    void inorder(struct Node *u){ 
        if(u == NIL) return;
        inorder(u->left);
        
        printf(" %d",u->key); 
        inorder(u->right);
        } 
        
void preorder(struct Node *u){ 
    if(u == NIL) return; 
     printf(" %d",u->key); 
            
    preorder(u->left);
    
    preorder(u->right);
            } 
            
            
 int main(){ 
    int n,i,x; 
    char com[20]; 
    scanf("%d",&n); 
        
    for(i=0;i<n;i++){
    scanf("%s",com);
          
    if(com[0] == 'f'){ 
        
        scanf("%d",&x);
        struct Node *t = find(root,x);
        
       if(t != NIL)    
        printf("yes\n");
        
         else printf("no\n"); 
                            
        } 
        
                        
        else if(com[0] == 'i'){
    scanf("%d",&x); insert(x);
    } 
        else if(com[0] == 'p'){
    inorder(root);
    printf("\n"); 
    preorder(root);
    printf("\n"); 
    }  
    else if(com[0] == 'd'){
      scanf("%d", &x);
      delete(find(root, x));
    }
             
         } 
    
    return 0; 
 }


Measured memory_bytes: 20516
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int>X[10000]; int N, M, A, B; bool ok = false; queue<char>Q;
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A >> B; if (A > B) { ok = true; } X[A].push_back(B);
	}
	if (ok == false) { cout << "0" << endl; return 0; }
	for (int i = 0; i < N; i++) {
		Q.push(i); int cnt = 0;
		while (!Q.empty()) {
			cnt++; if (cnt >= 1000000) { cout << "1" << endl; return 0; }
			int a1 = Q.front(); Q.pop();
			for (int j = 0; j < X[a1].size(); j++) {
				Q.push(X[a1][j]);
			}
		}
	}
	cout << "0" << endl;
	return 0;
}

Measured memory_bytes: 10436
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s[3];
	while (cin >> s[0]) {
		if (s[0] == "0")
			break;
		cin >> s[1] >> s[2];
		if (s[0][0] != '+' && s[0][0] == s[0][1] && s[0][1] == s[0][2]) {
			cout << s[0][0] << endl;
			continue;
		}
		if (s[1][0] != '+' && s[1][0] == s[1][1] && s[1][1] == s[1][2]) {
			cout << s[1][0] << endl;
			continue;
		}
		if (s[2][0] != '+' && s[2][0] == s[2][1] && s[2][1] == s[2][2]) {
			cout << s[2][0] << endl;
			continue;
		}
		if (s[0][0] != '+' && s[0][0] == s[1][0] && s[1][0] == s[2][0]) {
			cout << s[0][0] << endl;
			continue;
		}
		if (s[0][1] != '+' && s[0][1] == s[1][1] && s[1][1] == s[2][1]) {
			cout << s[0][1] << endl;
			continue;
		}
		if (s[0][2] != '+' && s[0][2] == s[1][2] && s[1][2] == s[2][2]) {
			cout << s[0][2] << endl;
			continue;
		}
		if (s[0][0] != '+' && s[0][0] == s[1][1] && s[1][1] == s[2][2]) {
			cout << s[0][0] << endl;
			continue;
		}
		if (s[0][2] != '+' && s[0][2] == s[1][1] && s[1][1] == s[2][0]) {
			cout << s[0][2] << endl;
			continue;
		}
		cout << "NA" << endl;
	}
	return 0;
}

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

int main(){
	int a=0;
  char s[110];
  for(int i=0; i<110; i++){
  	s[i] = 0;
  }
  do {
  	cin >> s[a];
    a++;
  }while(s[a-1] != 0);
    for(int i=0; i<a-1; i++){
    	cout << "x";
    }
}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
wv.sort(key = lambda x:x[1],reverse = True)
res = 0
tmp = min(n,5)
for i in range(tmp):
    dp = [[0] * (t+5) for _ in range(n+5)]
    for j in range(n):
        w,v = wv[j]
        for k in range(t):
            if k < w or i == j:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-w] + v)
    # print(dp[n][t-1])
    res = max(dp[n][t-1] + wv[i][1], res)
print(res)

Measured memory_bytes: 332268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef pair<pl,ll> ln;
map<ln,ll> bs;
const ll M = 998244353;
ll mul(ll a, ll b) {return (a*b)%M;}
ll bp(ll b, ll p) {
	ll ac = 1;
	while(p) {
		if(p&1) {ac = mul(ac,b);}
		b = mul(b,b);
		p >>= 1;
	}
	return ac;
}
ll gcd(ll a, ll b) {
	if(!a) return b;
	if(!b) return a;
	return gcd(b,a%b);
}
ll rnf(ll v) {
	ll s = 0,e = 220;
	while(s <= e) {
		ll m = (s+e)/2;
		if(m*(m-1) == v) {return m;}
		if(m*(m-1) > v) {
			e = m-1;
		} else {
			s = m+1;
		}
	}
	return -1;
}
pl v[220];
int main() {
	ios::sync_with_stdio(0);
	ll n;
	cin >> n;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		v[i] = {a,b};
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(i == j) continue;
			pl f = v[i];
			pl s = v[j];
			ll dx = f.first-s.first;
			ll dy = f.second-s.second;
			ll g = gcd(abs(dx),abs(dy));
			dx /= g;dy /= g;
			ll a = dy,b = -dx;
			if(a < 0) {a *= -1;b *= -1;} else if(a == 0) {
				b = abs(b);
			}
			ll c = -(a*f.first+b*f.second);
			ln e = {{a,b},c};
			bs[e]++;
		}
	}
	ll tot = bp(2,n);
	for(auto& it: bs) {
		ln sb = it.first;
		//cout << sb.first.first << "*x + " << sb.first.second << "*y + " << sb.second << " = 0\n";
		//cout << "ct " << rnf(it.second) << '\n';
		ll tc = rnf(it.second);
		ll ct = bp(2,tc);
		ct -= tc+1;
		tot -= ct;
	}
	tot -= n+1;
	tot = ((tot%M)+M)%M;
	cout << tot << '\n';
}

Measured memory_bytes: 1792
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A=sc.nextLong();
		long B=sc.nextLong();
		long C=sc.nextLong();
		long D=sc.nextLong();

		long ans_sum=B-A+1;
		long ans_div_c=B/C-A/C;
		long ans_div_d=B/D-A/D;
		long cd=C*D/gcd(C,D);
		long ans_div_cd=B/cd-A/cd;
		if (A%C==0) {
			ans_div_c+=1;
		}
		if (A%D==0) {
			ans_div_d+=1;
		}
		if (A%cd==0) {
			ans_div_cd+=1;
		}
		System.out.println(ans_sum-ans_div_c-ans_div_d+ans_div_cd);
	}

	static long gcd(long a,long b) {
	    long temp;
	    while ((temp=a%b)!=0) {
	        a=b;
	        b=temp;
	    }
	    return b;
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

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

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

signed main() {
  ll X, N;
  cin >> X >> N;

  map<ll, ll> m;
  rep(i, N) {
    ll p;
    cin >> p;
    m[p]++;
  }

  rep(i, 200) {
    ll a = X - i;
    ll b = X + i;

    if (m[a] == 0) {
      COUT(a);
      return 0;
    }
    if (m[b] == 0) {
      COUT(b);
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 3728
import itertools

A = [0 for i in range(5)]
for i in range(5):
    A[i] = int(input())
    
ans = 1000
for perm in itertools.permutations(A):
    this_ans = 0
    for a in perm[:-1]:
        if a % 10 == 0:
            this_ans += a
        else:
            this_ans += (a//10 + 1) * 10
    this_ans += perm[-1]
    ans = min(ans, this_ans)

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
    using namespace std;
    signed main(){
    int a[10],b,q=0;
    for(int i=0;i<5;i++){
    cin>>a[i];
    }
    cin>>b;
    for(int i=0;i<5;i++){
    for(int j=i+1;j<5;j++){
    if(abs(a[i]-a[j])>b){
    cout<<":(\n";
    q=1;
    break;
    }
    if(q==1) break;
    }
    }
    if(q==0) cout<<"Yay!\n";
    }

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String ans = help(s)?"YES":"NO";
        System.out.println(ans);
    }
    static boolean help(String s){
        String t = s.replace("A","");
        if(!t.equals("KIHBR")) return false;
        int[] rec = new int[5];
        int k=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!='A') rec[k++]=i;
        }
        return rec[0]<=1&&(rec[1]-rec[0]==1)&&(rec[2]-rec[1]==1)&&(rec[3]-rec[2]<=2)&&(rec[4]-rec[3]<=2)&&(s.length()-1-rec[4]<=1);
    }
}


Measured memory_bytes: 22868
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(i % 2 == 0){
            if(s[i] == 'L'){
            cout << "No" << endl;
            return 0;
            }
        }
        else{
            if(s[i] == 'R'){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int N,X;
    cin >> N >> X;
    
    if(500*N >= X) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<sstream>

using namespace std;

typedef long long int lint;

int main(int argc,char** args){

    lint n1;
    lint n2;

    cin>>n1;

    while(!cin.eof()){
        cin>>n2;

        lint sum=n1+n2;

        ostringstream temp;
        temp<<sum;

        string instr=temp.str();
        cout<<instr.length()<<endl;

        cin>>n1;
    }
    

    /* Lets try straight forward way first.
    string s1;
    string s2;

    cin>>s1;
    while(!cin.eof()){
        cin>>s2;
        
        int d1=s1[0];
        int d2=s2[0];

        //lets make sure s1 length is hight or equal
        if(s1.length() < s2.length*(){
            string swit=s2;
            s2=s1;
            s1=s2;
        }

        if(s1
        //if it the last digit, the for sure.
        if(d1+d2>9){

        }



        cin>>s1;
    }

    */

}

Measured memory_bytes: 1212
H,W=map(int,input().split())
m = [[0] for i in range(H+2)]
m[0] += [0]*W + [0]
for i in range(1,H+1):
  m[i]+=list(input().replace('.','0')) + [0]
m[H+1]+= [0]*W + [0]


for i in range(1,H+1):
  ans=''
  for j in range(1,W+1):
    if m[i][j] != '#':
      count = 0
      if m[i-1][j-1]=='#':count+=1
      if m[i-1][j  ]=='#':count+=1
      if m[i-1][j+1]=='#':count+=1
      if m[i  ][j-1]=='#':count+=1
      if m[i  ][j+1]=='#':count+=1
      if m[i+1][j-1]=='#':count+=1
      if m[i+1][j  ]=='#':count+=1
      if m[i+1][j+1]=='#':count+=1
      m[i][j] = count
    ans+=str(m[i][j])
  print(ans)





Measured memory_bytes: 3192