akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>using vv = vector<vector<T>>; template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

using TP = pair<pair<int, int>, int>;
using Q = pair<pair<int, int>, TP>;

int N, M;
vv<int> graph;
vector<ll> dist;
vv<bool> visited;

void bfs_kkp(int s, int t) {
    dist.assign(graph.size(), LINF);
    dist[s] = 0;
    queue<Q> que;
    que.emplace(mp(s, 0), TP(mp(-1, -1), -1));

    while (!que.empty()) {
        auto& q = que.front();
        int& v = q.first.first;
        int& d = q.first.second;
        TP& h = q.second;

        if (d % 3 == 0) {
            dist[v] = d / 3;

            //if (v == t) break;
        }

        for (int u : graph[v]) {
            if (visited[u][d % 3] == false) {
                visited[u][d % 3] = true;
                que.emplace(mp(u, d + 1), TP(mp(h.first.second, h.second), v));
            }
        }

        que.pop();
    }
}

int main() {
    cin >> N >> M;
    graph.resize(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        graph[u - 1].push_back(v - 1);
    }
    int S, T;
    cin >> S >> T;

    visited = vvec(N, 3, false);
    bfs_kkp(S - 1, T - 1);
    
    if (dist[T - 1] == LINF) {
        write(-1);
    }
    else {
        write(dist[T - 1]);
    }
}

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

const int mxn = 262150;
const int mxl = 1e5 + 1;
int n, q, v[mxn], w[mxn], dp[513][mxn];
	
int main() {
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> v[i] >> w[i];
	}
	for (int i=1; i<=min(511, n); i++) {
		int p = i / 2;
		for (int j=0; j<mxl; j++) {
			dp[i][j] = dp[p][j];
			if (j - w[i] >= 0) {
				dp[i][j] = max(dp[i][j], dp[p][j - w[i]] + v[i]);
			}
		}
	}
	cin >> q;
	while (q--) {
		int u, l;
		cin >> u >> l;
		vector<int> path;
		while (u > min(511, n)) {
			path.push_back(u);
			u /= 2;
		}
		int sz = path.size();
		int ans = 0;
		for (int i = 0; i < (1 << sz); i++) {
			int tw = 0, tv = 0;
			for (int j = 0; j < sz; j++) {
				if (i & (1 << j)) {
					tw += w[path[j]];
					tv += v[path[j]];
				}
			}
			if (l - tw >= 0) {
				ans = max(ans, dp[u][l - tw] + tv);
			}
		}
		cout << ans << '\n';
	}
}

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

long long int a[100001][3];
long long int n;
long long int memo[100001][3];
long long int solve(long long int i,long long int ind)
{
	if(i>=n)
		return 0;
	if(memo[i][ind]!=-1)
	{
		return memo[i][ind];
	}
	
	long long int ans=0;
	if(ind==0)
	{
		ans=max(ans,solve(i+1,1)+a[i][1]);
		ans=max(ans,solve(i+1,2)+a[i][2]);
	}
	else if(ind==1)
	{
		ans=max(ans,solve(i+1,0)+a[i][0]);
		ans=max(ans,solve(i+1,2)+a[i][2]);
	}
	else
	{
		ans=max(ans,solve(i+1,0)+a[i][0]);
		ans=max(ans,solve(i+1,1)+a[i][1]);
	}
	memo[i][ind]=ans;
//	cout<<ans<<"  ";
	return memo[i][ind];
}
int main()
{
	cin>>n;
	for(long long int i=0;i<n;i++)
	{
		for(long long int j=0;j<3;j++)
		{
			cin>>a[i][j];
		}
	}
	memset(memo,-1,sizeof(memo));
	long long int ans=max(solve(0,0),max(solve(0,1),solve(0,2)));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<class F>auto recursive(F f){return[f](auto...a){return f(f,a...);};}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int p;fixprec(int p):p(p){}}; ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.p);}
/*!* [intutil] *!*/
/*+* 整数演算いろいろ *+*/
i64 divceil(i64 a, i64 b) {
    return a / b + (a > 0 && a % b ? 1 : 0);
}
i64 logceil(i64 a, i64 b) {
    for(i64 i = 0, x = 1; a >= 2; x *= a, i++) if(x <= b) return i; return 0;
}
i64 gcd(i64 a, i64 b) {
    for (i64 c; a;) c = a, a = b % a, b = c; return b;
}
i64 lcm(i64 a, i64 b) {
    return (a / gcd(a, b) * b);
}
i64 pmod(i64 x, i64 m) {
    return (x % m + m) % m;
}

/*!* [prime] *!*/
/*+* 素数生成、素因数分解 *+*/

// 素数列を作る
// N: 上限, v: 出力先
struct PrimeSet {
    static vector<i64> p;
    static void Init(i64 N) {
        i64 c = 1;
        for (i64 c = 2; c <= N; c++) {
            bool flag = true;
            i64 d = (i64)sqrt(c);
            for (int i = 0; i < p.size(); i++) {
                if (c % p[i] == 0) {
                    flag = false;
                    break;
                }
                if (d < p[i]) break;
            }
            if (flag) p.push_back(c);
        }
    }
};

vector<i64> PrimeSet::p;
// 素因数分解を行う
// N: 対象, p: 素数セット(GetPrimesで取得), m: 因数分解形式のマップ
void Factorize(i64 N, map<i64, int> &m) {
    vector<i64> &p = PrimeSet::p;
    for (int i = 0; N != 1 && i < p.size(); i++) {
        while (N % p[i] == 0) {
            if (!m.count(p[i])) m[p[i]] = 0;
            N /= p[i];
            m[p[i]]++;
        }
    }
    if (N > 1) m[N] = 1;
}

int main() {
    int N;
    cin >> N;
    bool pairwise = true;
    PrimeSet::Init(2e3);
    vector<i64> A(N);
    for(i64 &a : A) cin >> a;
    i64 g = A[0];
    for(i64 a : A) {
        g = gcd(g, a);
    }
    for(i64 p : PrimeSet::p) {
        int c = 0;
        for(i64 &a : A) {
            if(a == 1) continue;
            if(a % p == 0) c++;
            while(a % p == 0) {
                a /= p;
            }
        }
        if(c > 1) {
            pairwise = false;
            break;
        }
    }
    map<i64, int> m;
    for (i64 a : A) m[a]++;
    for (auto x : m) {
        if (x.first != 1 && x.second > 1) {
            pairwise = false;
            break;
        }
    }
    if(pairwise) {
        cout << "pairwise coprime" << endl;
        return 0;
    }
    if(g == 1) {
        cout << "setwise coprime" << endl;
    } else {
        cout << "not coprime" << endl;
    }
    return 0;
}



Measured memory_bytes: 42172
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define mkp make_pair
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005
using namespace std;
/*
ll bin(ll i,ll j){
	ll mid=(i+j)/2;
	if(a[mid]==x)reutrn mid;
	else if(ans>x)return bin(i,mid-1);
	else return bin(mid+1,j);
}/*
ll power(ll base,ll power){
    ll res=1;
    base=base%mod;
    while(power>0){
    	if(power&1){
    		res=(res*base)%mod;
		}
		power=power>>1;
		base=(base*base)%mod;
	}
	return res;
}
*/
/*
int nCr(int x, int y){
	if(y>x)return 0;
	int num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}
*/
/*bool prime[n+1];
void SieveOfEratosthenes(int n){
	rep(i,0,n+1)prime[i]=true
    for (int p=2;p*p<=n;p++)
        if (prime[p])
            for (int i=p*p;i<=n;i+=p)prime[i]=false;
}*/
/*
int gcd(int a,int b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
*/

int dp[3002][3002];
string s,p;

int solve(){
	cin>>s>>p;
	rep(i,1,s.length()+1){
		rep(j,1,p.length()+1){
			if(s[i-1]==p[j-1])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
		}
	}
//	cout<<dp[s.length()][p.length()]<<endl;
	int i=s.length();
	int j=p.length();
	string ans="";
	while(dp[i][j]!=0){
		while(dp[i][j]==max(dp[i][j-1],dp[i-1][j])){
			if(dp[i][j]==dp[i-1][j])i--;
			else j--;
		}
		ans=p[j-1]+ans;
		i--;j--;
	}
	cout<<ans<<endl;
	return 0;
}
int main(){
    waste;
    int t;
//    cin>>t;
    t=1;
    while(t--){
       	solve();
    }
}


Measured memory_bytes: 35456
#include<bits/stdc++.h>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
using namespace std;
 /*temp*/
 
 
int main(){
	int a, b;
	cin >> a >> b;
	cout << a*b << " "<< 2*(a+b) << "\n";
	return 0;
}

Measured memory_bytes: 3004
using System;
using System.IO;
using System.Linq;
using System.Runtime;
using System.Reflection;
using System.Diagnostics;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;
using static System.Math;

class P
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
        string s = Console.ReadLine();
        string t = Console.ReadLine();

        long lcm = Lcm(nm[0], nm[1]);
        Dictionary<long, char> dict = new Dictionary<long, char>();
        long len = lcm / t.Length;
        for (int i = 0; i < t.Length; i++)
        {
            dict.Add(len * i, t[i]);
        }

        len = lcm / s.Length;
        for (int i = 0; i < s.Length; i++)
        {
            if (dict.ContainsKey(len * i))
            {
                if(dict[len * i] != s[i])
                {
                    Console.WriteLine(-1);
                    return;
                }
            }
        }
        Console.WriteLine(lcm);
    }

    static long Lcm(long a, long b)
    {
        return a * b / Gcd(a, b);
    }

    static long Gcd(long a, long b)
    {
        if (a < b) return Gcd(b, a);
        while (b != 0)
        {
            var remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }
}

Measured memory_bytes: 20064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[100010];
int par[100010];
int rk[100010];

void init(int n) {
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    rk[i] = 0;
  }
}

int find(int x) {
  if (par[x] == x)
    return x;
  else return par[x] = find(par[x]);
}

void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) {
    return;
  }
  if (rk[x] < rk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
  }
}

bool same(int x, int y) {
  return find(x) == find(y);
}

int main(){
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    unite(x, y);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (same(p[i], i)) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1408
import java.util.*;

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

class Solve{
	Scanner in = new Scanner(System.in);

	void solve(){
		int n = in.nextInt(), m = in.nextInt();
		int[] c = new int[m];
		for(int i= 0; i < m; i++) c[i] = in.nextInt();

		int[] t = new int[n + 1];
		for(int i = 0; i <= n; i++) t[i] = 100000000;
		t[0] = 0;

		for(int i = 0; i < m; i++){
			for(int j = c[i]; j <= n; j++){
				t[j] = Math.min(t[j], t[j-c[i]]+1);
			}
		}

		System.out.println(t[n]);
	}
	
}

Measured memory_bytes: 26776
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;
use std::usize;

fn main() {
    let n: usize = read();
    let uvw: Vec<(usize, usize, usize)> = (0..n - 1).map(|_| (read(), read(), read())).collect();

    let mut tree = vec![vec![]; n + 1];
    let mut colors = vec![None; n + 1];

    for (u, v, w) in uvw {
        tree[u].push((v, w));
        tree[v].push((u, w));
    }
    dfs(&tree, &mut colors, 1, 0);

    println!(
        "{}",
        colors
            .iter()
            .skip(1)
            .map(|x| x.unwrap().to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

fn dfs(
    tree: &Vec<Vec<(usize, usize)>>,
    colors: &mut Vec<Option<usize>>,
    position: usize,
    distance: usize,
) {
    colors[position] = if distance % 2 == 0 { Some(0) } else { Some(1) };

    for &(v, w) in tree[position].iter() {
        if colors[v].is_none() {
            dfs(tree, colors, v, distance + w);
        }
    }
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 23164
n = int(input())

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

ans = 0
mincost = [2001] * n
flag = [0] * n
mincost[0] = 0

while 1:
    v = -1
    for j in range(n):
        if flag[j] != 1 and (v == -1 or mincost[j] < mincost[v]):
            v = j
    if v == -1:
        break
    flag[v] = 1
    ans += mincost[v]
    for j in range(n):
        if a[v][j] == -1:
            continue
        mincost[j] = min(mincost[j], a[v][j])
print(ans)


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

# + - + - ...
cost1, sum1 = 0, 0
for i, a in enumerate(A):
	sum1 += a
	#print(sum1, cost1)
	if not i % 2:
		if sum1 <= 0:
			cost1 += (1 - sum1)
			sum1 = 1
	else:
		if 0 <= sum1:
			cost1 += (1 + sum1)
			sum1 = -1
#print(sum1, cost1)

# - + - + ...
cost2, sum2 = 0, 0
for i, a in enumerate(A):
	sum2 += a
	if i % 2:
		if sum2 <= 0:
			cost2 += (1 - sum2)
			sum2 = 1
	else:
		if 0 <= sum2:
			cost2 += (1 + sum2)
			sum2 = -1

print(min(cost1, cost2))


Measured memory_bytes: 14468
import itertools


def main():
    _ = int(input())
    d = list(map(int, input().split()))

    comb = itertools.combinations(d, 2)

    ans = 0
    for v in comb:
        ans += v[0] * v[1]

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
package main

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

var scanner = bufio.NewScanner(os.Stdin)

// const (
// 	initialBufSize = bufio.MaxScanTokenSize //65536
// 	maxBufSize     = 100000
// )
func main() {
	scanner.Split(bufio.ScanWords)
	// buf := make([]byte, initialBufSize)
	// scanner.Buffer(buf, maxBufSize)

	n, k := nextInt(), nextInt()

	sum := 0.0
	for i := 1; i <= n; i++ {
		if i >= k {
			sum += 1 / float64(n)
		} else {
			count := 0
			for j := i; j < k; j *= 2 {
				count++
			}
			sum += (1 / float64(n)) * math.Pow(0.5, float64(count))
		}
	}
	fmt.Println(sum)
}

func next() string {
	scanner.Scan()
	return scanner.Text()
}
func nextInt() int {
	i, err := strconv.Atoi(next())
	if err != nil {
		fmt.Println(err)
	}
	return i
}


Measured memory_bytes: 640
N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

count = 0
Added_list = []
for i in range(M):
    B,C = BC[i]
    Added_list += [C]*B
    count += B
    if count>N:
        Added_list = Added_list[:N]
        break

A += Added_list
A.sort(reverse=True)
print(sum(A[:N]))


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

enum PS = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971,991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381].to!(string[]);

void main()
{
    writeln(PS[0..readln.chomp.to!int].join(" "));
}

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

int dp[80000][11];//i????????§???????????°?????????mod 11 = j????????????????????°
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    while(cin >> s && s != "0"){
        int n = s.size();
        memset(dp, 0, sizeof(dp));
        rep(i, n){
            int k = s[i] - '0';
            if(k != 0) dp[i][k] = 1;
            if(i == 0) continue;
            rep(j, 11) dp[i][(j * 10 + k) % 11] += dp[i - 1][j];
        }
        int ans = 0;
        rep(i, n) ans += dp[i][0];
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1e9 + 7

template < typename T >
void printVector (const vector < T > & vec) {
	for (const T x : vec) {
		cout << x << " ";
	}
	cout << endl;
}

template < typename T >
void printMatrix (const vector < vector < T > > & mat) {
	for (const vector < T > vec : mat) {
		printVector (vec);
	}
	cout << endl;
}

const ll INF = 1e18L + 5;

template < typename T >
void min_self (T& a, T b) {
	a = min (a, b);
}

template < typename T >
void max_self (T& a, T b) {
	a = max (a, b);
}

void add_self (int & a, int b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int main() {
	int n, k;
	scanf ("%d %d", &n, &k);
	vector < int > a (n);
	for (int & x : a) scanf ("%d", &x);
	vector < bool > dp (k + 1, false);
	// dp[i] = true => player 1 wins if there are i stones in the pile
	// else player 2 wins
	// Initially we can't take any stone, so player two wins
	for (int stones = 0; stones <= k; stones++){
		for (int x : a) {
			if (stones >= x && !dp[stones - x]) {
				dp[stones] = true;
			}
		}
	}

	puts (dp[k] ? "First" : "Second");
	return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
import collections

N, M = list(map(int, input().split()))
ab_list = []

for _ in range(M):
    a, b = list(map(int, input().split()))
    ab_list.append(a)
    ab_list.append(b)

counter = collections.Counter(ab_list)
for i in range(N):
    print(counter[i + 1])


Measured memory_bytes: 3316
#include <stdio.h>
int main(void){
  int i, n, m, a[100], sum, counter;
  
  if( scanf("%d %d",&n ,&m)==1 );
  for(i=0;i<n;i++) if( scanf("%d",&a[i])==1 );
  
  sum = 0;
  for(i=0;i<n;i++) sum += a[i];
  
  counter = 0;
  for(i=0;i<n;i++)
    if(a[i] * 4 * m  >= sum)
      counter++;
  
  if(counter >= m)
    printf("Yes");
  else
    printf("No");
  
  return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> res;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) {
            num++;
            n /= p;
        }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));

    return res;
}

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

int main() {
    ll A, B;
    cin >> A >> B;
    ll G = gcd(A, B);
    auto pf = prime_factorize(G);
    cout << pf.size() + 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <fstream>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
#include <cassert>
#pragma warning (disable: 4996)
using namespace std;

using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

ll ll_gcd(ll a, ll b) {
    if (a < b) return ll_gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

struct UnionFind {
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    if (n < 0)return 0;
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

ll merge_cnt(vector<ll>& a) {
    int n = a.size();
    if (n <= 1) { return 0; }

    ll cnt = 0;
    vector<ll> b(a.begin(), a.begin() + n / 2);
    vector<ll> c(a.begin() + n / 2, a.end());

    cnt += merge_cnt(b);
    cnt += merge_cnt(c);

    int ai = 0, bi = 0, ci = 0;
    while (ai < n) {
        if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {
            a[ai++] = b[bi++];
        }
        else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }
    return cnt;
}

int main() {
    ll n;
    cin >> n;
    if (n > 999)cout << "ABD" << endl;
    else cout << "ABC" << endl;
}

Measured memory_bytes: 3604
s = input()[::-1]
n = len(s)
l = 0
ok = True
while l <n:
    ok_list = ["maerd","remaerd","resare","esare"]
    if s[l:l+5] in ok_list:
        l +=5
    elif s[l:l+6] in ok_list:
        l+=6
    elif s[l:l+7] in ok_list:
        l+=7
    else:
        ok = False
        break
if ok:print('YES')
else:print('NO')
    


Measured memory_bytes: 40432
#include <stdio.h>

using namespace std;

int main(){
	int r,c,sum,total_sum = 0;
	scanf("%d %d",&r,&c);
	int table[r+1][c+1];

	for(int i = 0; i < r+1; i++){
		for(int j = 0; j < c+1; j++){
			table[i][j] = 0;
		}
	}

	for(int i = 0; i < r; i++){
		sum = 0;
		for(int j = 0; j < c; j++){
			scanf("%d",&table[i][j]);
			sum += table[i][j];
			table[r][j] += table[i][j];
		}
		table[i][c] = sum;
		total_sum += sum;
	}
	table[r][c] = total_sum;

	for(int i = 0; i < r+1; i++){
		for(int j = 0; j < c; j++){
			printf("%d ",table[i][j]);
		}
		printf("%d\n",table[i][c]);
	}
}


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

using namespace std;

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

int main(void){
    int n = 5;
    vector<int> a(n);
    for(int i = 0; i < n; i++)cin >> a[i];
    int point = 0;
    int minj = 9;
    for(int i = 0; i < n; i++){
        if(a[i] % 10 == 0)continue;
        if(chmin(minj, a[i] % 10)){
            point = i;
        }
    }
    swap(a[point], a[4]);
    int order = 0, next = 0;
    int time;
    for(time = 0; ; time++){
        if(order == 0 && next == 5)break;
        if(order == 0 && time % 10 == 0){
            order += a[next++];
        }
        if(0 < order){
            order--;
        }
    }
    cout << time << endl;
}

Measured memory_bytes: 256
import sys
N, M = map(int, input().split())

num = []
for i in range(N) :
  num.append([0])

sc = []
for i in range(M) :
  sc.append(list(map(int, input().split()))) 

ans = ""

for n in sc :
  if n[1] not in num[n[0]-1] :
    num[n[0]-1].append(n[1])

if N >= 2 and [1, 0] in sc :
  print('-1')
  sys.exit()
elif N == 1 and num[0] == [0] :
  print('0')
  sys.exit()  
elif N >= 2 and num[0] == [0] :
  num[0].append(1)

for m in num :
  if len(m) >= 3 :
    print('-1')
    sys.exit()

if len(num[0]) == 1 :
  print('-1')
  sys.exit()
else :
  for l in range(N) :
    ans = ans + str(max(num[l]))

print(ans)

Measured memory_bytes: 3064
num=int(input())
height=list(map(int,input().split()))

dp=[0]*(num)
dp[1]=abs(height[1]-height[0])
for i in range(2,num):
  dp[i]=min(dp[i-1]+abs(height[i]-height[i-1]),dp[i-2]+abs(height[i]-height[i-2]))
print(dp[-1])

Measured memory_bytes: 13980
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << endl
#define print10(ele) cout << fixed << setprecision(10) << (ele) << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  char c[2][3];
  REP(i, 2) REP(j, 3) cin >> c[i][j];

  REP(i, 2) {
    REP(j, 3) {
      if (c[i][j] != c[1 - i][2 - j]) {
        print("NO");
        return 0;
      }
    }
  }
  print("YES");
  return 0;
}

Measured memory_bytes: 256
import numpy as np

a, b, h, m = map(int, input().split())
theta1 = np.pi * (30 * h + m / 2) / 180
theta2 = np.pi * m / 30
x1 = a * np.sin(theta1)
x2 = b * np.sin(theta2)
y1 = a * np.cos(theta1)
y2 = b * np.cos(theta2)
ans = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (0.5)
print(ans)


Measured memory_bytes: 27164
#include<stdio.h>
#define MAX 100000
#define NO -1

void ans(int);
void depth(int,int);

  long int p[MAX];
  long int l[MAX];
  long int r[MAX];

int n,Dp[MAX];

int main(){

  int d,v,c,le,ri;
  int i,j;

  scanf("%d",&n);

  for(i = 0; i < n; i++) p[i] = l[i] = r[i] = NO;

  for(i = 0; i < n; i++){
    scanf("%d%d",&v,&d);

    for(j = 0; j < d; j++){
      scanf("%d",&c);
      if(j == 0) l[v] = c;
      else r[le] = c;
      le = c;
      p[c] = v;
    }
  }

  for(i = 0; i < n; i++){
    if(p[i] == NO) ri = i;
  }

  depth(ri,0);

  for(i = 0; i < n; i++) ans(i);

  return 0;

}

void ans(int a){
  int i,b;
  printf("node %d: ",a);
  printf("parent = %d, ",p[a]);
  printf("depth = %d, ",Dp[a]);

  if(p[a] == NO) printf("root, ");
  else if(l[a] == NO) printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i = 0, b = l[a]; b != NO; i++, b = r[b]){
    if(i != 0) printf(", ");
    printf("%d",b);
  }

  printf("]\n");
}

void depth(int a, int i){
  Dp[a] = i;
  if(r[a] != NO) depth(r[a],i);
  if(l[a] != NO) depth(l[a],i+1);
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=1001;
pll cor[mxn];
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
char d[]={'R','U','L','D'};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	int odd = 0;
	for(int i=0; i<n; i++){
		ll x,y;
		cin >> x >> y;
		cor[i].fi = x;
		cor[i].se = y;
		if((x+y)%2)odd++;
	}
	vll bt;
	if(odd==n){ // all odd
		bt.eb(1LL);
		for(int i=1; i<31; i++)bt.eb(bt.back()*2LL);
	}else if(odd==0){ // all even
		bt.eb(1LL);
		bt.eb(1LL);
		for(int i=1; i<31; i++)bt.eb(bt.back()*2LL);
	}else{
		cout << -1 << endl;
		return 0;
	}
	int m = bt.size();
	cout << m << endl;
	for(auto x:bt)cout << x << ' '; cout << endl;
	for(int i=0; i<n; i++){
		ll x = cor[i].fi;
		ll y = cor[i].se;
		string s="";
		for(int j=m-1; j>=0; j--){
			for(int k=0; k<4; k++){
				ll X = x+(ll)dx[k]*bt[j];
				ll Y = y+(ll)dy[k]*bt[j];
				if(ll(abs(X)+abs(Y))<=(ll)bt[j]){
					s+=d[k];
					x = X; y = Y;
					break;
				}
			}
		}
		reverse(all(s));
		cout << s << endl;
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


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

#define MOD 1000000007
#define f first
#define s second
#define es " "
#define pb push_back
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define ll long long int
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int main(){
    fastio;
    int n, v[100005], resp=0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    sort(v, v+n);
    cout << v[n/2]-v[(n/2)-1] << endl;
    return 0;
}

Measured memory_bytes: 640
var lines = [];

var readline = require("readline");
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on("line", function (x) {
    lines.push(x);
});

rl.on("close", function () {
    var N = Number(lines[0]); lines.shift();
    var SP = lines.map(i => i.split(" "))
    var arr = []

    for (var i = 0; i < N; i++) {
        var s = SP[i][0]; var p = SP[i][1];
        arr.push({ i: i + 1, s, p });
    }

    arr.sort((a, b) => {
        if (a.s < b.s) { return (-1); }
        else if (a.s > b.s) { return (1) }
        else { return (b.p - a.p) }
    });
    
    for (var i = 0; i < N; i++) {
        console.log(arr[i].i)
    }
});

Measured memory_bytes: 8372
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<string>
#include<vector>

#define ll long long
#define ull unsigned long long

using namespace std;
int main(void) {
	ll A = 0, B = 0, C = 0, X = 0;
	scanf("%lld%lld%lld%lld", &A, &B, &C, &X);
	printf("%lld\n", X % 2 == 0 ? A - B : B - A);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>

#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
//#define for(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define print(x) std::cout << x << std::endl;

using namespace std;

typedef long long ll;

template<class T, class U> std::string replace(std::string s, const T& target, const U& replacement, bool replace_first = 0, bool replace_empty = 0);
bool isContain(int value, int under, int top);
vector<int> range(int x);

int main(void) {
	//Program Start

	vector<int> annt(5);
	rep(i,5){
		cin >> annt[i];
	}

	int k;
	cin >> k;

	if(annt[4] - annt[0] > k) {
		cout << ":(" << endl;
	} else {
		cout << "Yay!" << endl;
	}



ProgramEndPointLabel:;

	//Program End
	//system("pause");

	return 0;
}


vector<int> range(int y) {
	vector<int> result(y);
	for (int i = 0; i < y; i++)
		result[i] = i;
	return result;
}

bool isContain(int value, int under, int top) {
	if (under <= value && value <= top) return true;
	return false;
}

template<class T, class U> std::string replace(std::string s, const T& target, const U& replacement, bool replace_first, bool replace_empty) {
	using S = std::string;
	using C = std::string::value_type;
	using N = std::string::size_type;
	struct {
		auto len(const S& s) { return s.size(); }
		auto len(const C* p) { return std::char_traits<C>::length(p); }
		auto len(const C  c) { return 1; }
		auto sub(S* s, const S& t, N pos, N len) { s->replace(pos, len, t); }
		auto sub(S* s, const C* t, N pos, N len) { s->replace(pos, len, t); }
		auto sub(S* s, const C  t, N pos, N len) { s->replace(pos, len, 1, t); }
		auto ins(S* s, const S& t, N pos) { s->insert(pos, t); }
		auto ins(S* s, const C* t, N pos) { s->insert(pos, t); }
		auto ins(S* s, const C  t, N pos) { s->insert(pos, 1, t); }
	} util;

	N target_length = util.len(target);
	N replacement_length = util.len(replacement);
	if (target_length == 0) {
		if (!replace_empty || replacement_length == 0) return s;
		N n = s.size() + replacement_length * (1 + s.size());
		s.reserve(!replace_first ? n : s.size() + replacement_length);
		for (N i = 0; i < n; i += 1 + replacement_length) {
			util.ins(&s, replacement, i);
			if (replace_first) break;
		}
		return s;
	}

	N pos = 0;
	while ((pos = s.find(target, pos)) != std::string::npos) {
		util.sub(&s, replacement, pos, target_length);
		if (replace_first) return s;
		pos += replacement_length;
	}
	return s;
}


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

#define MOD 1000000007

int n;
int a[200005];
long long sum;
long long ans;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}
	for (int i = 0; i < n; i++) {
		sum -= a[i];
		ans += (sum % MOD) * (a[i] % MOD);
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4496
#include <iostream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))

using namespace std;

int main(void)
{
	int N; cin >> N;
	vector<pair<int, int>> r(N), b(N);
	rep(i, 0, N) {
		int x, y; cin >> x >> y;
		r[i].first = y;
		r[i].second = x;
	}
	rep(i, 0, N)cin >> b[i].first >> b[i].second;
	sort(r.begin(), r.end()); sort(b.begin(), b.end());
	int ans = 0;
	vector<bool> p(N, false);
	rep(i,0,N) {
		int j = N - 1;
		while (j >= 0 && (r[j].second >= b[i].first || r[j].first >= b[i].second || p[j]==true)) j--;
		if (j >= 0) {
			ans++;
			p[j] = true;
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 764
n=int(input())
h=list(map(int,input().split()))
a=0
max=0
for i in range(1,n):
    if h[i]<=h[i-1]:
        a+=1
        if i==n-1 and a>max:
            max=a
    elif a>max:
        max=a
        a=0
    else:
        a=0
print(max)


Measured memory_bytes: 63856
n = gets.to_i
edge = (n-1).times.map{gets.split.map(&:to_i)}
vert = (0..n).map{[]}
colors = []

edge.each.with_index{|(a,b),i|
  vert[a] << [b,i]
  vert[b] << [a,i]
}
q = [1,0,0]
while q[0]
  a,parent,parent_color = q.pop
  color = (parent_color==1)? 2 : 1
  vert[a].each{|b,i|
    next if b == parent
    colors[i] = color
    q << [b,a,color]
    color += 1
    color += 1 if color == parent_color
  }
end
p colors.max
puts colors

Measured memory_bytes: 29100
s = input()
if s[0] == "A" and s[2:len(s)-1].count("C") == 1 and s.count("A") == 1 and s.count("C") == 1:
        if (str(s[1:s.find("C")])+str(s[s.find("C")+1:len(s)])).islower():
                print("AC")
        else:
                print("WA")
else:
        print("WA")

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int mod = 1e9 + 7;
const int N = 2010;
int n, m, k, ans;
int dp[N];

int main() {
    fill(dp, dp + N, 1);
    dp[0] = dp[1] = dp[2] = 0;
    cin >> n;
    for (int i = 3; i <= n; ++i) {
        for (int j = i - 3; j >= 0; --j) {
            dp[i] = (dp[i] + dp[j]) % mod;
        }
    }
    cout << dp[n] << endl;
    return 0;
}


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

using namespace std;

const long long mod = 1e9 + 7;

long long n, k, in, ans = 1;
vector<long long> a, b, temp;

void solve() {
	cin >> n >> k;
	for (long long i = 0; i < n; ++i) {
		cin >> in;
		if (in < 0) {
			b.push_back(in);
		} else {
			a.push_back(in);
		}
	}
	if (n == k) {
		for (long long i = 0; i < a.size(); ++i) {
			ans *= a[i], ans %= mod;
		}
		for (long long i = 0; i < b.size(); ++i) {
			ans *= b[i], ans %= mod;
		}
		ans += mod, ans %= mod;
		cout << ans << endl;
	} else if (!a.size() && k % 2) {
		for (long long i = 0; i < a.size(); ++i) {
			temp.push_back(a[i]);
		}
		for (long long i = 0; i < b.size(); ++i) {
			temp.push_back(-b[i]);
		}
		sort(temp.begin(), temp.end());
		for (long long i = 0; i < k; ++i) {
			ans *= temp[i];
			ans %= mod;
		}
		cout << (-ans % mod) + mod << endl;
	} else {
		sort(a.begin(), a.end());
		sort(b.begin(), b.end(), greater<long long>());
		if (k % 2) {
			ans *= a.back();
			a.pop_back();
		}
		while (a.size() >= 2) {
			long long x = a.back();
			a.pop_back();
			x *= a.back();
			a.pop_back();
			temp.push_back(x);
		}
		while (b.size() >= 2) {
			long long x = b.back();
			b.pop_back();
			x *= b.back();
			b.pop_back();
			temp.push_back(x);
		}
		sort(temp.begin(), temp.end(), greater<long long>());
		for (long long i = 0; i < k / 2; ++i){
			ans *= temp[i] % mod, ans %= mod;
		}
		cout << ans << endl;
	}
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    //freopen("input.txt", "r", stdin);
	solve();
    return 0;
}

Measured memory_bytes: 6596
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
import bisect


def read():
    N = int(input().strip())
    AB = []
    for i in range(N):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, AB


def solve(N, AB, MOD=1000000007):
    A = list(sorted([a for a, b in AB]))
    B = list(sorted([b for a, b in AB]))
    if N % 2 == 1:
        m = N // 2
        low = A[m]
        high = B[m]
        return high - low + 1
    else:
        m = N // 2
        low = A[m-1] + A[m]
        high = B[m-1] + B[m]
        return high - low + 1
    return -1


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 41152
use proconio::input;

fn main() {
    input! {
        n: i32,
        m: usize,
        xs: [i32; m],
    };

    let sum = xs.iter().fold(0, |acc, x| acc + x);

    if sum <= n {
        println!("{}", n - sum);
    } else {
        println!("{}", -1);
    }
}


Measured memory_bytes: 2236
def main():
    N = int(input())
    for h in range(1, 3501):
        for n in range(1, 3501):
            denominator = 4*h*n - N*n - N*h
            if denominator <= 0:
                continue
            w = (N*h*n)/denominator
            if w % 1 == 0:
                print(h, n, int(w))
                exit()


if __name__ == "__main__":
    main()


Measured memory_bytes: 9200
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, PII> PPII;
typedef pair<int, PPII> PPPII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int N, K;
	vector<int> g[10];
	vector<ll> sum[10];
	ll dp[10][2020] = {};
	ll res =0;
	cin >> N >> K;
	REP(i, N){
		int C, G;
		cin >> C >> G;
		g[G-1].push_back(C);
	}
	REP(i, 10){
		sum[i].push_back(0);
		sort(all(g[i]), greater<int>());
		REP(j, g[i].size()){
			sum[i].push_back(sum[i][j]+g[i][j]+2*j);
		}
	}
	REP(i, sum[0].size()){
		dp[0][i] = sum[0][i];
	}
	REP(i, 9){
		REP(j, K){
			REP(k, sum[i+1].size()){
				if(k-1 > j) break;
				dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j-k+1]+sum[i+1][k]);
			}
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
		}
	}
	cout << dp[9][K] << endl;
}

Measured memory_bytes: 3264
/* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 
                                                           
*/
/* }}} */

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

// #define int long long

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define print(x) cout << x << '\n'
#define Fi first
#define Se second

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = 1; i <= (n); i++)
#define DEPS(i, a, n) for (int i = (a); i >= n; i--)
#define DEP(i, n) for (int i = (n); i >= 0; i--)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* const */
const int INF = 999999999;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool is_uruu(int y) {return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;}
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}

/* }}} */

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

  for (int n; cin >> n, n; ){
    vi p(n), j(n - 1);

    REP(i, n) cin >> p[i];
    REP(i, n - 1) cin >> j[i];

    ll sum = accumulate(p.begin(), p.end(), 0) + accumulate(j.begin(), j.end(), 0);
    ll ans = sum;

    sort(j.begin(), j.end());
    REP(i, n - 1){
      sum -= j[i];
      ans = max(ans, sum * (i + 2));
    }
    print(ans);
  }

  return 0;
}

Measured memory_bytes: 1532
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <map>
#include <stdio.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
void chmin(int &a, int b) { if (a > b) a = b; }

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll MOD = (ll)pow(10.0, 9.0) + 7;
pint dx[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
char da[4] = { 'R', 'L', 'D', 'U' };
char dax[4] = { -1, 1, -1, 1 };
char dax2[4] = { 1, -1, 1, -1 };
ll min(ll a, ll b)
{

	return (a < b) ? a : b;
}
ll max(ll a, ll b) { return (a > b) ? a : b; }


template<typename T, T MOD = 1000000007>
struct Mint {
	T v;

	Mint() : v(0) {}
	Mint(signed v) : v(v) {}
	Mint(ll t) { v = t % MOD; if (v < 0) v += MOD; }

	Mint pow(ll k) {
		Mint res(1), tmp(v);

		while (k) {

			if (k & 1) res *= tmp;

			tmp *= tmp;
			k >>= 1;
		}



		return res;
	}

	Mint inv() { return pow(MOD - 2); }

	Mint& operator=(Mint a) { if (a.v >= MOD) a.v %= MOD; v = a.v; return *this; }
	Mint& operator+=(Mint a) { v += a.v; if (v >= MOD) v -= MOD; return *this; }
	Mint& operator-=(Mint a) { v += MOD - a.v; if (v >= MOD) v -= MOD; return *this; }
	Mint& operator*=(Mint a) { v = 1LL * v * a.v % MOD; return *this; }
	Mint& operator/=(Mint a) { return (*this) *= a.inv(); }
	Mint operator+(Mint a) const { return Mint(v) += a; }
	Mint operator-(Mint a) const { return Mint(v) -= a; }
	Mint operator*(Mint a) const { return Mint(v) *= a; }
	Mint operator/(Mint a) const { return Mint(v) /= a; }

	Mint operator-() { return v ? MOD - v : v; }
	bool operator==(const Mint a) const { return v == a.v; }
	bool operator!=(const Mint a) const { return v != a.v; }
	bool operator < (const Mint a) const { return a < a.v; }


};

using M = Mint<ll>;

M inv1, inv2, inv3;

M Fact[2 * 10000005];
M calc_E(ll H, ll W, ll K) { return M(H) * M(K) * inv1;    }
M calc_V(ll H, ll W, ll K) { return M(H + W - K)*M(K)*M(W)*M(H)*inv2 ; }
M calc_ans(ll H, ll W, ll K) { 
	M e = calc_E(H, W, K), v = calc_V(H, W, K);
	return M(K + 1) * (e + 1) - e - e * e - v; 
}

int main() {
	ll H, W, K;
	
	Fact[0] = 1;
	cin >> H >> W >> K;
	inv1 = M(1) / M(H + W);
	inv2 = M(1) / (M(H + W - 1) * M(H + W) * M(H + W));
	
	
	rep(i, H + W + 10) {

		Fact[i + 1] = Fact[i] * (i + 1);
	}

	inv3 = M(1) / Fact[H + W - K];
	M ans = 0;

	rep(i, K) {
	
		ans += Fact[H+W]*inv3*calc_ans(H, W, i+1);
		
	}

	cout << ans.v << endl;
	return 0;

}

Measured memory_bytes: 156544
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double PI = 3.14159265358979;
const double E = 2.718281828459045;
const double root2 = sqrt(2);
typedef pair<int, int> P;
typedef unsigned int ui;
const ll key = 998244353;
struct dat { int tim; int pc; int stu; int log; };
int main() {
	int n, m;
	while (cin >> n >> m,n) {
		int r; cin >> r;
		vector<dat> D; int a, b, c, d;
		for (int i = 0; i < r; i++) {
			cin >> a >> b >> c >> d;
			D.push_back({ a,b,c,d });
		}
		int q; cin >> q; int s, t, u;
		for (int i = 0; i < q; i++) {
			cin >> s >> t >> u;
			int tab[1000] = {}; int cnt = 0;
			for (int j = 0; j < r; j++) {
				if (D[j].stu == u) {
					if (D[j].log == 0) {
						tab[D[j].tim+1-540]--;
					}
					else {
						tab[D[j].tim-540]++;
					}
				}
			}
			for (int j = 1; j < 1000; j++) {
				tab[j] += tab[j - 1];
			}
			for (int j = s-540; j < t-540; j++) {
				if (tab[j] > 0&&tab[j+1]>0)cnt++;
			}
			cout << cnt << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3148
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 998244353
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, a, b, k;
int ans;
int kaii[300010];

int ccomb(int x, int y) {
	return kaii[x] * mod_pow(kaii[x - y], mod - 2, mod) % mod*mod_pow(kaii[y], mod - 2, mod) % mod;
}

signed main() {
	cin >> n >> a >> b >> k;
	kaii[0] = 1;
	for (int i = 1; i <= n+1; i++)kaii[i] = kaii[i - 1] * i%mod;
	for (int i = 0; i <= n; i++) {
		if ((k - a * i) % b != 0 || (k - a * i) / b<0 || (k - a * i) / b>n)continue;
		int j = (k - a * i) / b;
		ans += ccomb(n, i)*ccomb(n, j);
		ans %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560