akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    long h,w,d;
    long x,y,xy;
    long hikaku[3] = {999};
    while (1) {
        
        hikaku[0] = 999;
        hikaku[1] = 999;
        hikaku[2] = 8999999;
        scanf("%ld %ld",&h,&w);
        if (h==0 && w==0) {
            break;
        }
        
        d=(h*h)+(w*w);
        
        for (y=1; y<=150; y++) { //????????´???
            for (x=y+1;x<=150; x++) {
                xy = (x*x) + (y*y);
                
                if (h==y && w==x) {
                    continue;
                }

                if (d <= xy) {
                    
                    if (d == xy) {
                        
                        if (hikaku[2] > xy && y>=h) {
                            hikaku[0] = x;
                            hikaku[1] = y;
                            hikaku[2] = xy;
                        }
                        
                        if (y>=h && hikaku[1] > y) {
                            hikaku[0] = x;
                            hikaku[1] = y;
                            hikaku[2] = xy;
                        }
                    }
                    
                    if (hikaku[2] > xy && d < xy) {
                        hikaku[0] = x;
                        hikaku[1] = y;
                        hikaku[2] = xy;
                    }
                    
                }
            }
        }
    printf("%ld %ld\n",hikaku[1],hikaku[0]);
            
    }
    return 0;
}

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

int main(){
  int h,n;
  cin >> h >> n;
  vi a(n);
  rep(i,n) cin >> a.at(i);
  int sum = 0;
  rep(i,n) sum += a.at(i);
  if(sum >= h) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
class program{
  static void Main(){
    int[] xn = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
    if(xn[1] == 0){
      Console.Write(xn[0]);
      return;
    }
    int[] p = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
    if(!p.Contains(xn[0])){
      Console.Write(xn[0]);
      return;
    }
    for(byte i = 1;i < 101;i++){
      if(!p.Contains(xn[0]-i)){
        Console.Write(xn[0]-i);
        return;
      }
      if(!p.Contains(xn[0]+i)){
        Console.Write(xn[0]+i);
        return;
      }
    }
  }
}

Measured memory_bytes: 27844
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>
using namespace std;


/*二つのボールの座標の差のベクトルをすべて計算し、最も多い組み合わせを(p,q)として採用すればよさそう*/
long long N, x[50], y[50];
vector< pair <long long, long long> > diff;

int main() {
    long long p,q;
    scanf("%lld", &N);
    for(int i=0;i<N;i++){
        scanf("%lld %lld", &x[i], &y[i]);
    }

    int num = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(j==i){
                continue;
            }
            p = x[i] - x[j];
            q = y[i] - y[j];
            
            diff.push_back(make_pair(p,q));
            num += 1;
        }
    }
    sort(diff.begin(), diff.end());

    long long p_prev, q_prev;
    p_prev = 0; q_prev = 0;
    int cont, cont_max;
    cont = 1;
    cont_max = 0;
    //printf("num = %d\n", num);
    for(int i=0;i<num;i++){
    	//printf("(%lld,%lld), prev=(%lld, %lld)\n", diff[i].first, diff[i].second, p_prev, q_prev);
        if(p_prev == diff[i].first && q_prev == diff[i].second){
            cont += 1;
            //printf("cont = %d\n", cont);
        }else{
            cont = 1;
            p_prev = diff[i].first;
            q_prev = diff[i].second;
        }
        if(cont_max < cont){
        	cont_max = cont;
        }
    }
    printf("%lld\n", N-cont_max);
}

Measured memory_bytes: 384
import java.util.*;

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



Measured memory_bytes: 35160
#include <stdio.h>

int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	
	if (a>b){
		printf("a > b\n");
	}
	else if (a<b){
		printf("a < b\n");
	}
	else{
		printf("a == b\n");
	}
	
	return 0;
}


Measured memory_bytes: 2056
// C - 755
#include <bits/stdc++.h>
using namespace std;

int N;
string S;
vector<int> A;

void dfs(int x, int depth){
	if(x > N) return;

	int a = x;
	set<int> s;
	while(a){
		s.insert(a%10);
		if(s.size() == 3) break;
		a /= 10;
	}

	if(s.size() == 3) A.push_back(x);

	if(depth >= S.size()) return;

	dfs(x*10+3, depth+1);
	dfs(x*10+5, depth+1);
	dfs(x*10+7, depth+1);
}

int main(){
	cin>>S;
	N = stoi(S);
	dfs(0, 0);
	cout<< A.size() <<endl;
}

Measured memory_bytes: 512
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            new Main().solve(sc);
        }
    }
 
    void solve(Scanner sc) {
        int n = sc.nextInt();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            while (a % 2 == 0 && a >= 2) {
                count++;
                a /= 2;
            }
        }
        System.out.println(count);
    }
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    int n, r, ans = 0;
    cin >> n >> r;
    ans = r + max(0, 100 * (10 - n));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
  while (true) {
    int N, M, P;
    cin >> N >> M >> P;

    if (N == 0) { break; }

    int atari_count;
    int ticket_count = 0;
    for (int i = 0; i < N; i++) {
      int input;
      cin >> input;
      ticket_count += input;
      if (i+1 == M) { atari_count = input; }
    }

    if (atari_count != 0) {
      printf("%d", 100 * ticket_count * (100 - P) / 100 / atari_count);
    } else {
      printf("0");
    }

    puts("");
  }
  return 0;
}

Measured memory_bytes: 1144
<?php
  list($n,$k) = explode(" ", trim(fgets(STDIN)));
  $cnt = intdiv($n, $k);
  $ans = $cnt**3;
  if($k % 2 == 1){
    echo $ans;
    exit;
  }
  $cnt2 = intdiv($n+$k/2, $k);
  $ans += $cnt2**3;
  echo $ans;




Measured memory_bytes: 16132
package main

// Solution for https://atcoder.jp/contests/abc074/tasks/abc074_a

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, a int
	con.Scan(&n, &a)
	con.Println(n*n - a)
	return nil
}


Measured memory_bytes: 1844
#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
char S[200005], T[200005];
int main() {
	int H, W, N;
	int sr, sc;
	scanf("%d%d%d%d%d%s%s", &H, &W, &N, &sr, &sc, S, T);
	auto check = [&](int M, int s, char l, char r) {
		int st = 1, en = M;
		for (int i = N - 1; i >= 0; --i) {
			if (st <= en) {
				if (T[i] == l) en = min(M, en + 1);
				else if (T[i] == r) st = max(1, st - 1);
			}
			if (S[i] == r) --en;
			else if (S[i] == l) ++st;
		}
		return !(st <= s && s <= en);
	};
	printf(check(H, sr, 'U', 'D') || check(W, sc, 'L', 'R') ? "NO\n" : "YES\n");
}


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

#define ll long long int
#define pb push_back
#define RONALDO            \
  ios::sync_with_stdio(0); \
  cin.tie(0);              \
  cout.tie(0);
#define endl "\n"
#define pii pair<ll, ll>
#define ff first
#define ss second
#define mod 1000000007
#define vi vector<ll>
#define mi map<char, ll>
#define Max(x, y, z) max(x, max(y, z))
#define Min(x, y, z) min(x, min(y, z))
//LOVE U MESSI && CRistiano !!

//INSPIRATIONAL MICHAEL PHELPS && USAIN BOLT !!

int main()
{
  RONALDO;
  ll n;
  cin >> n;
  ll a[n], b[n], ans = 0;
  vi v;
  for (ll i = 0; i < n; i++)
  {
    cin >> a[i];
  }
  b[0] = a[0];
  for (ll i = 1; i < n; i++)
  {
    b[i] =b[i - 1] + a[i];
  }
  for (ll i = 0; i < n - 1; i++)
  {
    ans += ((b[i]%mod) * (a[i + 1]%mod)) % mod;
  }
  cout << ans%mod;
}

Measured memory_bytes: 6620
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int n, m;
  cin >> n >> m;
  string t = "aaa";
  bool flag = true;
  rep(i, m) {
    int s;
    char c;
    cin >> s >> c;
    if (t[s - 1] == 'a' || t[s - 1] == c) {
      t[s - 1] = c;
    } else {
      flag = false;
    }
  }
  string ans;
  if (n == 3) {
    if (t[0] == '0') flag = false;
    if (t[0] == 'a') t[0] = '1';
    if (t[1] == 'a') t[1] = '0';
    if (t[2] == 'a') t[2] = '0';
    ans = t;
  } else if (n == 2) {
    if (t[0] != 'a' && t[1] != 'a' && t[2] != 'a') flag = false;
    if (t[0] == 'a' && t[2] == 'a') {
      if (t[1] == '1') {
        ans.push_back('1');
        ans.push_back('0');
      } else {
        ans.push_back('1');
        ans.push_back(t[1]);
      }
    }
    if (t[0] != 'a') {
      if (t[1] = 'a') t[1] = '0';
      ans.push_back(t[0]);
      ans.push_back(t[1]);
    }
    if (t[2] != 'a') {
      if (t[1] = 'a') t[1] = 1;
      ans.push_back(t[1]);
      ans.push_back(t[2]);
    }
  } else if (n == 1) {
    int count = 0;
    char b;
    rep(i, 3) {
      if (t[i] != 'a') {
        count++;
        b = t[i];
      }
    }
    if (count >= 2)
      flag = false;
    else if (count == 0)
      ans.push_back('0');
    else
      ans.push_back(b);
  }
  if (flag)
    cout << ans << endl;
  else
    cout << -1 << endl;
  return 0;
}

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

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define FI first
#define SE second
using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}

template <typename T>
T power(T a, T n, T mod) {
  T res = 1;
  T tmp = n;
  T curr = a;
  while(tmp){
    if(tmp % 2 == 1){
      res = (T)((ll)res * curr % mod);
    }
    curr = (T)((ll)curr * curr % mod);
    tmp >>= 1;
  }
  return res;
}

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll m, n;
  cin >> m >> n;
  cout << power<ll>(m, n, mod) << endl;
	return 0;
}



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

int main(void){

  long n;
  scanf("%ld", &n);
  long a[n];
  for (long i = 0; i < n; i++) {
    scanf("%ld", &a[i]);
  }
  long sum[n];
  sum[0] = a[0];
  for (long i = 1; i < n; i++) {
    sum[i] = sum[i-1]+a[i];
  }
  long all = sum[n-1];
  long other = all-sum[0];
  long min = labs(other-sum[0]);
  for (long i = 1; i < n-1; i++) {
    other = all-sum[i];
    if (labs(other-sum[i]) < min) {
      min = labs(other-sum[i]);
    }
  }
  printf("%ld\n", min);

  return 0;
}

Measured memory_bytes: 3328
from sys import stdin
def isWar_X(z, lst):
    for i in range(len(lst)):
        if lst[i] >= z:
            return True
    return False

def isWar_Y(z, lst):
    for i in range(len(lst)):
        if lst[i] < z:
            return True
    return False

def isWar(X, Y, xs, ys):
    for z in range(X+1, Y):
        if (not(isWar_X(z, xs)) and not(isWar_Y(z, ys))):
            return "No War"
    return "War"

N, M, X, Y = [int(x) for x in stdin.readline().rstrip().split()]
xs = [int(x) for x in stdin.readline().rstrip().split()]
ys = [int(x) for x in stdin.readline().rstrip().split()]
print(isWar(X,Y, xs, ys))


Measured memory_bytes: 3064
#include <cstdio>
#include <utility>
using namespace std;

#define gcu getchar_unlocked
#define ii inline int in
#define is inline bool scan
ii(int c) {
	int n = 0;
	bool minus = false; if (c == '-') minus = true, c = gcu();
	do {n = 10 * n + (c - '0'), c = gcu();} while (c >= '0');
	//return n; }
	return minus ? -n : n; }
ii() {return in(gcu());}
is(int &n){int c=gcu();return c==EOF?false:(n=in(c),true);}
is(char &c){c=gcu();gcu();return c!=EOF;}
//is(string &s){int c; s = "";
//	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#undef ii
#define pcu putchar_unlocked
template <typename T>
void out(T n) {
	static char buf[20];
	char *p = buf;
	if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
void out(const char *s){while(*s)pcu(*s++);}
void out(char c){pcu(c);}
//void out(string &s){for (char c: s) pcu(c);}
template <typename head, typename... tail>
void out(head&& h, tail&&... t){out(h);out(move(t)...);}
//template <typename T>
//void out(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
#undef svo

int main() {
	bool first = true;
	for (int a, b; a = in(), b = in(), a || b;) {
		if (first)
			first = false;
		else
			out('\n');
		bool f = false;
		for (int m = a % 4, i = a + (m ? 4 - m: 0); i <= b; i += 4)
			if (!(i % 400) || i % 100) {
				f = true;
				out(i, '\n');
			}
		out(f ? "" : "NA\n");
	}
}


Measured memory_bytes: 2536
# a,b = map(int, input().split())
n = int(input())

one = n % 10

if(one==2 or one==4 or one==5 or one==7 or one==9):
    print("hon")
elif(one==0 or one==1 or one==6 or one==8):
    print("pon")
else:
    print("bon")
        

Measured memory_bytes: 61616
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <map>
#include <complex>
#include <ctime>
#include <numeric>
#include <set>
 
using namespace std;
 
typedef long long ll;
 
typedef struct node{
    int s, e, val, pos;
    bool operator<(const node& n) const{
        if(e != n.e) return e < n.e;
        return val > n.val;
    }
    node(){};
    node(int ss, int ee, int v, int p){
        s = ss, e = ee, val = v, pos = p;
    }
}node;
 
int occs[(int)1e6 + 5], tree[500005], n, ans[500005];
 
void update(int x, int val){
    while(x <= n){
        tree[x] += val;
        x += x & -x;
    }
}
 
int query(int x){
    int ret = 0;
    while(x > 0){
        ret += tree[x];
        x -= x & -x;
    }
    return ret;
}
 
int main()
{
 
    int q, s, e;
    vector<node> v;
    scanf("%d", &n);
    scanf("%d", &q);
    for(int i = 1; i <= n; i++){
        scanf("%d", &s);
        v.push_back(node(i, i, s, -1));
    }
    for(int i = 0; i < q; i++){
        scanf("%d %d", &s, &e);
        v.push_back(node(s, e, 0, i));
    }
 
    sort(v.begin(), v.end());
 
    for(int i = 0;i < v.size(); i++){
        if(v[i].val == 0){
            ans[v[i].pos] = query(v[i].e) - query(v[i].s - 1);
        }else{
            if(occs[v[i].val] != 0) update(occs[v[i].val], -1);
            update(v[i].s, 1);
            occs[v[i].val] = v[i].s;
        }
    }
 
    for(int i = 0; i < q; i++){
        printf("%d\n", ans[i]);
    }
 
    return 0;
}
 

Measured memory_bytes: 25308
#include<cstdio>
using namespace std;
int main(){
    int l[11]={0};
    char unk;
    while(scanf("%d",&l[1])!=EOF){
        scanf(" %c",&unk);
        for(int i = 2;i <= 10; i++)scanf("%d %c",&l[i],&unk);
        double v1,v2;
        scanf("%lf,%lf",&v1,&v2);

        double sum=0,a;
        for(int i = 1;i <= 10; i++)sum += (double)l[i];

        a = sum/(v1+v2)*v1;
        sum = 0;
        bool f = 0;
        for(int i = 1;i <= 10; i++){
            sum += l[i];
            if(a <= sum){
                printf("%d\n",i);
                f = 1;
            }
            if(f == 1)break;
        }
    }
    return 0;
}

Measured memory_bytes: 1056
#include <bits/stdc++.h>
using namespace std;
int main(){
  map<int,int> ma;
  int n,m,k;
  cin>>n>>m>>k;
  int d[m],u[101]={};
  for(int i=0;i<m;i++){cin>>d[i];d[i]--;ma[d[i]]=i,u[d[i]]=1;}
  vector<int>v[n];
  for(int i=0;i<n;i++)for(int j=0,x;j<k;j++){cin>>x;x--;v[i].push_back(x);}
  int dp[1<<m],INF=1<<29;
  fill(dp,dp+(1<<m),INF);
  dp[(1<<m)-1]=0;
  queue<int> que;
  que.push((1<<m)-1);
  while(!que.empty()){
    int t=que.front();que.pop();
    for(int j=0;j<k;j++){
      int r=0;
      for(int i=0;i<m;i++){
        if(t&(1<<i)){
          int x=v[d[i]][j];
          if(u[x])r|=1<<ma[x];
        }
      }
      if(dp[r]>dp[t]+1)dp[r]=dp[t]+1,que.push(r);
    }
  }
  cout<<dp[0]<<endl;
  return 0;
}


Measured memory_bytes: 3532
def D():
    n = int(input())
    ans = 0
    # for i in range(1, n+1):
    #     m = 0
    #     s = [i for i in range(1, n+1)]
    #     for j in range(len(s)):
    #         m = max(m, s[0]%i)
    #         del s[0]

    #     print(i, m)
    #     ans += m
    ans = n*(n-1)//2
    print(ans)
D()

Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;

int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int dx = tx - sx, dy = ty - sy;
	string str;
	str += string(dx, 'R');
	str += string(dy + 1, 'U');
	str += string(dx + 1, 'L');
	str += string(dy + 1, 'D');
	str += "RD";
	str += string(dx + 1, 'R');
	str += string(dy + 1, 'U');
	str += string(dx + 1, 'L');
	str += string(dy, 'D');
	cout << str << endl;
}


Measured memory_bytes: 256
#include <iostream> 
using namespace std;
typedef long long ll;

const int MAX_A = 1000010;
int divisor[MAX_A];

int sieve(int n){
    for (int i = 2; i <= n; ++i) divisor[i] = i;
	for (int i = 2; i <= n; i++){
		if (divisor[i] == i){
			for (int j = i+i; j <= n; j += i) {
                divisor[j] = i;
			}
		}
	}
    return 0;
}

int gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a%b);
}

int main() {
    int N, g;
    bool is_pairwise = true, mod[1000010];
    for (int i = 2; i < 1000000; ++i) mod[i] = false;
    sieve(1000000);
    
    cin >> N;
    for (int i = 0; i < N; ++i){
        int a;
        cin >> a;
        if (i == 0){
            g = a;
        }else{
            g = gcd(a, g);
        }

        while (a != 1){
            int t = divisor[a];
            if (mod[t]) is_pairwise = false;
            mod[t] = true;
            while(a%t==0) a/=t;
        }
    }

    if (is_pairwise){
        cout << "pairwise coprime" << endl;
    } else if (g == 1){
        cout << "setwise coprime" << endl;
    }else {
        cout << "not coprime" << endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair<int, int>pi;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef pair<P, P> PPP;

const ll MOD = 1e9 + 7;
const ll INF = 9e18;
const double DINF = 5e14;
const double eps = 1e-10;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

int hirosi, kenzirou, h1, h2, k1, k2, a, b, c, d;
int main() {
	cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;
	hirosi = h1 * a + h2 * b + h1 / 10 * c + h2 / 20 * d;
	kenzirou = k1 * a + k2 * b + k1 / 10 * c + k2 / 20 * d;
	if (hirosi == kenzirou)cout << "even" << endl;
	else if (hirosi > kenzirou)cout << "hiroshi" << endl;
	else cout << "kenjiro" << endl;
	return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int n,h;
int a[100000],b[100000];
int main()
{
	cin>>n>>h;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
	}
	sort(a,a+n);
	sort(b,b+n);
	int ans=0;
	for(int i=n-1;i>=0;i--)
	{
		if(h<=0)
		{
			cout<<ans;
			return 0;
		}
		if(b[i]>a[n-1])
		{
			ans++;
			h-=b[i];
		}
		else
		break;
	}
	ans+=(h+a[n-1]-1)/a[n-1];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b){
    if(a < b){
        return gcd(b, a);
    }
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main() {
  int n, k, x, m, g;
  vector<int> a(100001);
  cin >> n >> k;

  cin >> x;
  m = x;
  g = x;
  for (int i = 0; i < n-1; i++) {
    cin >> x;
    if (x > m) m = x;
    g = gcd(g, x);
  }

  if (k <= m && k%g==0) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <string>
#include <cctype>
#include <cstdio>
#include <math.h>
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
const int AMAX = 100000; 
using namespace std;
#define rep(i, n) for (i64 i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (i64 i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define fst first
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sw swap
#define UP(x) transform(x.begin(), x.end(), x.begin(), ::toupper);
#define down(x) transform(x.begin(), x.end(), x.begin(), ::tolower);
using LL = long long;
using ULL = unsigned long long;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main(void) {
    LL n,k,a,b;
    cin >>n>>k;
    rep(i, n){
    cin >> b;
    if(k <= b){
        a += 1;
    }
    }
    cout << a;
}

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

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define zeroend __builtin_ctz
#define ones __builtin_popcount
#define ends "\n"
#define space ' '
typedef long long ll;
typedef pair<int, int> pii;

/*
void solve(int i, int j, string s){
	if(i==0)
		ans.insert(s2.substr(0, j)+s);
	else if(j==0)
		ans.insert(s1.substr(0, i)+s);
	else if(s1[i-1]==s2[j-1])
		solve(i-1, j-1, s1[i-1]+s);
	else{
		if(dp[i-1][j]<=dp[i][j-1])
			solve(i-1, j, s1[i-1]+s);
		if(dp[i-1][j]>=dp[i][j-1])
			solve(i, j-1, s2[j-1]+s);
	}
}*/


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

	for(int i=1; i<n; ++i){
		for(int j=0; j<i; ++j){
			if(a[j]>a[i]&&low[i]<high[j]+1)
				low[i]=high[j]+1;
			else if(a[j]<a[i]&&high[i]<low[j]+1)
				high[i]=low[j]+1;
		}
		ans=max({ans, low[i], high[i]});
	}

	cout << ans << ends;


*/

const int N = 100, N2 = 1e5;

ll dp[N2+1];
//array<ll, 3> dp;
//set<string> ans;
//vector<int> low(N, 1), high(N, 1);
ll v[N], m[N];

int n, w;

int main(){
	cin >> n >> w;
	for(int i=0; i<n; ++i)
		cin >> m[i] >> v[i];
		
	for(int i=1; i<=n; ++i){
		for(int j=w; j>=m[i-1]; --j)
			dp[j]=max(dp[j], v[i-1]+dp[j-m[i-1]]);
	}


	cout << dp[w] << ends;
}


Measured memory_bytes: 4280
n,k,q=map(int,input().split())
#a=[0 for i in range(n)]
c=[k-q for i in range(n)]
for i in range(q):
  b=int(input())
  c[b-1]+=1
for i in c:
  if i<=0:
    print("No")
  else:
    print("Yes")

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

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 998244353ll;
const ll MAXN = (ll) 5e3 + 10;
const ll INF = (ll) 1e17;
const ld EPS = (ld) 1e-8;

pll a[MAXN];

bool CMP(pll x, pll y){
	ll upx, upy;
	upx = x.F;
	upy = y.F;
	upx = min(upx, y.F - x.S);
	upy = min(upy, x.F - y.S);
	return upx > upy;
}

ll dp[2][MAXN];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	ll n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i].F >> a[i].S;
	sort(a, a + n, CMP);
	
	//for(int i = 0; i < n; i++) cerr << a[i].F << ' ' << a[i].S << '\n';
	
	for(int i = 0; i < 2;i++) fill(dp[i], dp[i] + n + 1, INF);
	
	dp[0][0] = 0;
	for(int i = 1; i <= n; i++){
		//fill(dp[i & 1], dp[i & 1] + n + 1, INF);
		dp[i & 1][0] = 0;
		for(int j = 1; j <= n; j++){
			dp[i & 1][j] = INF;
			dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j]);
			if(a[i - 1].F >= dp[i & 1 ^ 1][j - 1]){
				dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j - 1] + a[i - 1].S);
			}
		}
	}
	
	//debug(dp[0][3]);
	
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		if(dp[n & 1][i] != INF) ans = max(ans, (ll) i);
	}
	
	cout << ans;
	
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int t = sc.nextInt();
        
        int sumNum = 0;
        int minTime = 0;
        
        while (n > sumNum) {
        	sumNum += x; 
        	minTime += t;
        }
        
        System.out.println(minTime);

    }
}

Measured memory_bytes: 35840
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, m, l; cin >> n >> m >> l;
  vector<vector<long long>> matrixa(n, vector<long long>(m)), matrixb(m, vector<long long>(l)), ans(n, vector<long long>(l, 0));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++) cin >> matrixa[i][j];
  }
  for (int j = 0; j < m; j++){
    for (int k = 0; k < l; k++) cin >> matrixb[j][k];
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < l; j++){
      for (int k = 0; k < m; k++) ans[i][j] += matrixa[i][k] * matrixb[k][j];
    }
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < l; j++){
      cout << ans[i][j];
      if (j == l - 1) cout << endl;
      else cout << " ";
    }
  }
}


Measured memory_bytes: 3300
#include <stdio.h>
 
int main(){
    double a,b,c,d,e,f,A;
    double x,y;
    double AA[2][2];
 
    for(;scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f) == 6;){
        A = a*e-b*d;
        AA[0][0] = e/A;
        AA[0][1] = -b/A;
        AA[1][0] = -d/A;
        AA[1][1] = a/A;
        x = c*AA[0][0]+f*AA[0][1];
        y = c*AA[1][0]+f*AA[1][1];
        printf("%.3f %.3f\n",x,y);
    }
 
    return 0;
}

Measured memory_bytes: 652
#include <stdio.h>
int abc(int i) {
	int n;
	scanf("%d", &n);

	return n;
}
int main(void) {
	int i, n, r = 0;

	scanf("%d", &n);

	int s[100];

	for (i = 0; i < n; i++) {
		s[i] = abc(i);
	}
	for (i = 0; i < n && r == 0; i++) {
		if (s[i] % 2 == 0) {
			if ((s[i] % 3) != 0 && (s[i] % 5) != 0) {
				r = 1;
			}
		}
	}
	if (r == 0)
		puts("APPROVED");

	else
		puts("DENIED");

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
*/

string s;

bool kaibun(string t){
	int n = t.size();
	rep(i,n){
		if(t[i]!=t[n-1-i])return false;
	}
	return true;
}

int main(void){
	cin>>s;
	bool ok=true;
	int n = s.size();
	if(!kaibun(s))ok=false;
	if(!kaibun(s.substr(0,(n-1)/2)))ok=false;
	if(!kaibun(s.substr((n+3)/2-1)))ok=false;
	cout<<(ok?"Yes":"No")<<endl;
	return 0;
}

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

int main(){
    int c[3][3];
    for(int i=0;i<3;++i) {
        for(int j=0;j<3;++j) {
            cin >> c[i][j];
            }
        }
    string ans = "No";
    for (int a1=0;a1<=100;++a1) {
        int b1 = (c[0][0] - a1);
        int a2 = (c[1][0] - b1);
        int a3 = (c[2][0] - b1);
        int b2 = (c[1][1] - a2);
        int b3 = (c[1][2] - a2);
        if(a3 + b2 == c[2][1]
            && a3 + b3 == c[2][2]
            && a1 + b2 == c[0][1]
            && a1 + b3 == c[0][2]) {
                ans = "Yes";
                break;
            }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

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

        String s = stdIn.next();
        char[] cs = s.toCharArray();

        int q = stdIn.nextInt();

        boolean isReverse = false;
        ArrayList<Character> front = new ArrayList<Character>();
        ArrayList<Character> back = new ArrayList<Character>();
        int t, f;
        char[] temp;
        char c;
        for(int i=0; i<q; i++){
            t = stdIn.nextInt();
            if(t == 1){
                isReverse = (isReverse) ? false : true;
            }else{
                f = stdIn.nextInt();
                temp = stdIn.next().toCharArray();
                c = temp[0];
                if(((f == 1) && !isReverse) || ((f == 2) && isReverse)){
                    front.add(c);
                }else{
                    back.add(c);
                }
            }
        }

        if(!isReverse){
            for(int i=front.size()-1; i>=0; i--){
                System.out.print(front.get(i));
            }
            System.out.print(s);
            for(int i=0; i<back.size(); i++){
                System.out.print(back.get(i));
            }
        }else{
            for(int i=back.size()-1; i>=0; i--){
                System.out.print(back.get(i));
            }
            for(int i=cs.length-1; i>=0; i--){
                System.out.print(cs[i]);
            }
            for(int i=0; i<front.size(); i++){
                System.out.print(front.get(i));
            }
        }
    }
}

Measured memory_bytes: 154704
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bit = 0;
        for (int i=0; i<N; i++) {
            bit |= sc.nextInt();
        }
        System.out.println(Integer.numberOfTrailingZeros(bit));
    }
}


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

int main() {
  int n;
  cin >> n;

  for (int i = 0; i < n; i++) {
    string c;
    cin >> c;
    if (c == "Y") {
      cout << "Four" << endl;
      return(0);
    }
  }
  cout << "Three" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = (1 << 29);
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int main(int argc, char* argv[])
{
  int n;
  cin >> n;
  vector<int> nums(1e+5 + 5, 0);

  rep(i, n) {
    int a;
    cin >> a;
    nums[a]++;
  }

  int ans = 0;
  rep(i, 1e+5 + 3) {
    chmax(ans, nums[i] + nums[i+1] + nums[i+2]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
# ALDS1_3_D Areas on the Cross-Section Diagram

s = input()
s = list(s)  # 地形リスト

s1 = []  # \ リスト


class S2:
    # 池の位置と大きさのリスト
    def __init__(self):
        self.point = []
        self.size = []

    def append(self, x, y):
        lake_size = y
        if not self.point:  # 一番最初の池の処理
            self.point.append(x)
            self.size.append(lake_size)
        else:
            if self.point[-1] < x:
                self.point.append(x)
                self.size.append(lake_size)
            else:
                while self.point[-1] > x:
                    # print('w self.point:{} x:{}'.format(self.point[-1], x))
                    self.point.pop()
                    lake_size += self.size[-1]
                    self.size.pop()
                    if not self.point:
                        break
                self.point.append(x)
                self.size.append(lake_size)
        # print('append point:{} append size:{}'.format(self.point, self.size))
        return self

    def pop(self):
        x = self.point.pop()
        y = self.size.pop()
        return x, y

    def sum_size(self):
        sum_size = sum(self.size)
        return sum_size


s2 = S2()

for i in range(len(s)):
    if s[i] is '\\':
        s1.append(i)
    elif s[i] is '/':
        if s1:  # S1が空ではない場合
            lake_point = s1.pop()
            lake_size = i - lake_point
            # print('point : {} size : {}'.format(lake_point, lake_size))

            s2.append(lake_point, lake_size)

total = s2.sum_size()
lake_num = len(s2.size)

# print('total size : {} number of lakes : {}\nlake size\n{}'.format(total, lake_num, s2.size))
print(total)
print(lake_num, end='')
for i in range(len(s2.size)):
    print('', s2.size[i], end='')
print('')




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

using namespace std;

typedef long long ll;

int main()
{
    int N, A, B;
    cin >> N >> A >> B;

    int ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        string s = to_string(i);
        int sum = 0;
        for (int j = 0; j < s.size(); ++j)
        {
            sum += s[j] - '0';
        }
        if (sum >= A && sum <= B) ans += i;
    }
    cout << ans << endl;


    return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int std_in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};
const int MOD = 1000000007;

ll N, K;
ll g[200010];

ll powll(ll x){
    vector<ll> v;
    v.push_back(x);
    for(ll i = 1; (1 << i) <= N; i++){
        v.push_back(v[i - 1] * v[i - 1] % MOD);
    }
    ll ret = 1;
    for(ll i = 0; (1 << i) <= N; i++){
        if((1 << i) & N) ret = ret * v[i] % MOD;
    }
    return ret;
}


signed main(){
    cin >> N >> K;
    ll ans = 0;
    for(ll i = K; i > 0; i--){
        g[i] = powll(K / i);
        for(ll j = 2; j * i <= K; j++) g[i] = (g[i] - g[j * i] + MOD) % MOD;
        ans = (ans + g[i] * i) % MOD;
    }
    PRINT(ans);
    return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> way(M);
  for(int i = 0; i < M; i++){
    cin >> way.at(i).first >> way.at(i).second;
  }

  vector<int> count(N);
  for(pair<int,int> w : way){
    count.at(w.first - 1)++;
    count.at(w.second - 1)++;
  }
  
  for(int n : count){
    cout << n << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void)
{
   int n, i;
   double sum = 0, b[1000], av;
   while (1)
   {
       scanf("%d", &n);
       if (n == 0)
       {
           return 0;
       }
       for (i = 0; i < n; i++)
       {
           scanf("%lf", &b[i]);
           sum = sum + b[i];
       }
       av = sum / n;

       sum = 0;

       for (i = 0; i < n; i++)
       {
           sum = sum + (b[i] - av)*(b[i] - av);
       }
           printf("%f\n", sqrt(sum / n));
       sum = 0;


   }
}


Measured memory_bytes: 2716
/*#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
*/

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

#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 2e9 + 7;
const int MAX_N = 5e5 + 5;
int dx[] = { -(ll)1,0,(ll)1,0 }, dy[] = { 0,(ll)1,0,-(ll)1 };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = ll> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = (ll)1; while (b > 0) { if (b & (ll)1) { c = a * c%mod; }a = a * a%mod; b >>= (ll)1; }return c; }
inline void _nCr() { fac[0] = (ll)1; for (int i = (ll)1; i < MAX_N; i++) { fac[i] = fac[i - (ll)1] * i%mod; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], mod - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % mod)*inv[n - r] % mod; }
inline void PRI(ll n) { bool a[n + (ll)1]; for (int i = 0; i < n + (ll)1; i++) { a[i] = (ll)1; }for (int i = 2; i < n + (ll)1; i++) { if (a[i]) { prime.pb(i); ll b = i; while (b <= n) { a[b] = 0; b += i; } } } }

typedef pair<int, pair<int, int>> edge;

class UnionFind {
private:
	vector<int> par;
public:
	UnionFind(int N) { par = vector<int>(N, -(ll)1); }
	int find(int x);
	ll size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};



class Kruskal {
private:
	UnionFind *uf;
	vector<edge> e;
public:
	vector<edge> mst;
	Kruskal(int N) { uf = new UnionFind(N); }
	void add(int x, int y, ll z);
	void run();
};



//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

ll UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

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



//----Kruskal-------------------------------
void Kruskal::add(int x, int y, ll z) {
	//x < y
	if (x > y) swap(x, y);
	e.push_back({ z,{x,y} });
}

void Kruskal::run() {
	sort(e.begin(), e.end());
	e.erase(unique(e.begin(), e.end()), e.end());
	for (auto x : e) {
		if (uf->same(x.second.first, x.second.second)) {
			continue;
		}
		else {
			mst.push_back(x);
			uf->unite(x.second.first, x.second.second);
		}
	}
}

signed main() {
	string s;cin >> s;
	int cnt[26];
	REP (i,26) cnt[i] = 0;
	REP (i,s.size()) {
		cnt[(s[i] - 'a')]++;
	}
	ll ans = s.size() * (s.size () - 1) / 2;
	REP (i,26) {
		ans -= cnt[i] * (cnt[i] - 1) / 2;
	}
	cout << ++ans << endl;
}

Measured memory_bytes: 640
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum, k, q;
ll dat[ohara];

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

  cin >> n;
  rep(i, n) cin >> a[i];
  ll mi = LINF;
  ans = 1000;
  rep(i, n) {
    if (mi >= a[i]) {
      mi = min(mi, a[i]);
    } else {
      ll kabu = ans / mi;
      ans -= kabu * mi;
      mi = a[i];
      ans += kabu * a[i];
    }
  }
  Cout(ans);
  return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
typedef pair<int,int> pii;
typedef vector<int> vi;
const int INF = (1<<25);
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int w,h;
int sx,sy;
char room[20][21];
int res;

int dfs(int y,int x){
  room[y][x]='#';
  
  for(int i=0;i<4;i++){
    int ny=y+dy[i],nx=x+dx[i];
    if(0<=nx && nx<w && 0<=ny && ny<h && room[ny][nx]=='.'){
      res++;
      dfs(ny,nx);
    }
  }
}

int main(){
  while(cin>> w>> h,w){
    res=0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin>> room[i][j];
	if(room[i][j]=='@'){
	  sy=i; sx=j;
	}
      }
    }
    dfs(sy,sx);
    cout<< res+1<< endl;
  }
}

Measured memory_bytes: 1172
#include <iostream>
#include <string>
#include <algorithm>
#include <deque>

using namespace std;

class Dice
{
public:
	enum FACE
	{
		eTop = 0,
		eFront,
		eRight,
		eLeft,
		eBack,
		eBottom
	};

	Dice()
	{
	}

	Dice(bool isSetNumber)
	{
		if (isSetNumber)
		{
			SetDiceNumber();
		}
	}

	virtual ~Dice()
	{
	}

	void SetDiceNumber()
	{
		dqDiceNumber.resize(6);
		cin >> dqDiceNumber[eTop];
		cin >> dqDiceNumber[eFront];
		cin >> dqDiceNumber[eRight];
		cin >> dqDiceNumber[eLeft];
		cin >> dqDiceNumber[eBack];
		cin >> dqDiceNumber[eBottom];

		cin.clear();
		cin.ignore();
	}

	void OrderE()
	{
		deque<FACE>		Rotation{ eTop, eLeft, eBottom, eRight };

		OrderExecute(Rotation);
	}

	void OrderW()
	{
		deque<FACE>		Rotation{ eTop, eRight, eBottom, eLeft };

		OrderExecute(Rotation);
	}

	void OrderN()
	{
		deque<FACE>		Rotation{ eTop, eFront, eBottom, eBack };

		OrderExecute(Rotation);
	}

	void OrderS()
	{
		deque<FACE>		Rotation{ eTop, eBack, eBottom, eFront };

		OrderExecute(Rotation);
	}

	void OrderRotation()
	{
		deque<FACE>		Rotation{ eFront, eRight, eBack, eLeft };

		OrderExecute(Rotation);
	}

	int		GetDiceNumber(FACE face)
	{
		return (dqDiceNumber[face]);
	}

	void	SearchTop(int t)
	{
		for (int i = 0; i < 4; i++)
		{
			if (t == dqDiceNumber[eTop])
			{
				return;
			}
			OrderN();
		}

		for (int i = 0; i < 4; i++)
		{
			if (t == dqDiceNumber[eTop])
			{
				return;
			}
			OrderE();
		}
	}

	void	SearchFront(int f)
	{
		for (int i = 0; i < 4; i++)
		{
			if (f == dqDiceNumber[eFront])
			{
				return;
			}
			OrderRotation();
		}
	}

private:
	deque<size_t>	dqDiceNumber;

	void OrderExecute(const deque<FACE> &Rotation)
	{
		auto	temp = dqDiceNumber[Rotation[0]];
		auto	LoopMax = Rotation.size() - 1;

		for (auto i = 0u; i < LoopMax; i++)
		{
			dqDiceNumber[Rotation[i]] = dqDiceNumber[Rotation[i + 1]];
		}
		dqDiceNumber[Rotation[LoopMax]] = temp;
	}
};

void DiceI();

int main()
{
	DiceI();

	return 0;
}

void DiceI()
{
	Dice	d(true);

	string	str;

	getline(cin, str);
	for (auto it : str)
	{
		switch (toupper(it))
		{
		case 'S':
			d.OrderS();
			break;
		case 'N':
			d.OrderN();
			break;
		case 'E':
			d.OrderE();
			break;
		case 'W':
			d.OrderW();
			break;
		default:
			break;
		}
	}

	cout << d.GetDiceNumber(Dice::eTop) << "\n";
}

Measured memory_bytes: 3160
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author hsy
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task2 solver = new Task2();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task2 {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            String s = in.next();
            int[] a = new int[3];
            for (int i = 0; i < s.length(); i++) {
                a[s.charAt(i) - 'a']++;
            }
            int l = s.length() / 3 + (s.length() % 3 == 0 ? 0 : 1);
            for (int i = 0; i < 3; i++) {
                if (a[i] > l) {
                    out.println("NO");
                    return;
                }
            }
            out.println("YES");
        }

    }
}



Measured memory_bytes: 23636