akhauriyash/Code-Regression huggingface dataset:
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn dfs(x: usize, used: &mut [bool], assign: &mut [Option<usize>], g: &[Vec<usize>]) -> bool {
    used[x] = true;
    for &u in g[x].iter() {
        let ok = assign[u].map_or(true, |p| {
            !used[p] && dfs(p, used, assign, g)
        });
        if ok {
            assign[x] = Some(u);
            assign[u] = Some(x);
            return true;
        }
    }
    false
}

fn run() {
    input! {
        a: usize,
        b: usize,
        m: usize,
        e: [(usize, usize); m],
    }
    let mut g = vec![vec![]; a + b];
    for (x, y) in e {
        g[x].push(y + a);
        g[y + a].push(x);
    }
    let mut assign: Vec<Option<usize>> = vec![None; a + b];
    for x in 0..a {
        if assign[x].is_some() {
            continue;
        }
        let mut used = vec![false; a];
        dfs(x, &mut used, &mut assign, &g);
    }
    let ans = assign.iter().take(a).filter(|p| p.is_some()).count();
    println!("{}", ans);
}

fn main() {
    run();
}



Measured memory_bytes: 5048
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in)
		;
		for(;;){
			String s1 = sc.next();
			String s2 = sc.next();
			if(s2.equals("X"))break;
			String[]s=null;
			if(s1.contains("_")){
				s=s1.split("_");
			}
			else if('a'<=s1.charAt(0)&&s1.charAt(0)<='z'){
				StringBuffer sb=new StringBuffer();
				for(int i=0;i<s1.length();i++){
					if(Character.isUpperCase(s1.charAt(i))){
						sb.append(",");
						sb.append(s1.charAt(i));
					}
					else{
						sb.append(s1.charAt(i));
					}
				}
				
				s=sb.toString().split(",");
			}
			else{
				StringBuffer sb=new StringBuffer();
				sb.append(s1.charAt(0));
				for(int i=1;i<s1.length();i++){
					if(Character.isUpperCase(s1.charAt(i))){
						sb.append(",");
						sb.append(s1.charAt(i));
					}
					else{
						sb.append(s1.charAt(i));
					}
				}
				s=sb.toString().split(",");
			}
			StringBuffer sb=new StringBuffer();
			if(s2.equals("U")){
				for(int i=0;i<s.length;i++){
					for(int j=0;j<s[i].length();j++){
						if(j==0&&Character.isLowerCase(s[i].charAt(j))){
							int add=s[i].charAt(j)-32;
							sb.append((char)add);
						}
						else{
							sb.append(s[i].charAt(j));
						}
					}
					
				}
			}
			else if(s2.equals("L")){
				for(int i=0;i<s.length;i++){
					for(int j=0;j<s[i].length();j++){
						if(i!=0&&j==0&&Character.isLowerCase(s[i].charAt(j))){
							int add=s[i].charAt(j)-32;
							sb.append((char)add);
						}
						else if(i==0&&j==0&&Character.isUpperCase(s[i].charAt(j))){
							int add=s[i].charAt(j)+32;
							sb.append((char)add);
						}
						else{
							sb.append(s[i].charAt(j));
						}
					}
					
				}
				
			}
			else{
				for(int i=0;i<s.length;i++){
					for(int j=0;j<s[i].length();j++){
						if(j==0&&Character.isUpperCase(s[i].charAt(j))){
							int add=s[i].charAt(j)+32;
							sb.append((char)add);
						}
						else{
							sb.append(s[i].charAt(j));
						}
					}
					if(i==s.length-1){
						
					}
					else
					sb.append("_");
				}
				
			}
			System.out.println(sb);
		}
	}

}

Measured memory_bytes: 17220
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>

using namespace std;

void b_common_raccoon_vs_monster(void) {
	long long h, n;
	cin >> h >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		h -= a[i];
	}

	if (h <= 0) cout << "Yes" << endl;
	else        cout << "No" << endl;

}

int main()
{
    b_common_raccoon_vs_monster();

    return 0;
}

Measured memory_bytes: 3788
#include<iostream>
#include<queue>
using namespace std;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
struct state{ int ay,ax,by,bx,cnt; };
int H,W;
int t[50][50];
int visited[50][50][50][50];
bool inField(int y,int x){
  if(y<0||y>=H)return false;
  if(x<0||x>=W)return false;
  if(t[y][x]==1)return false;
  return true;
}
void solve(state s){
  queue < state > Q;
  Q.push(s);
  visited[s.ay][s.ax][s.by][s.bx]=true;
  while(!Q.empty()){
    state now = Q.front(); Q.pop();
    int ay=now.ay,ax=now.ax,by=now.by,bx=now.bx;
    if(now.cnt>100)continue;
    if(ay==by&&ax==bx){ cout<<now.cnt<<endl; return; }
    for(int i=0;i<4;i++){
      int nay=ay+dy[i],nax=ax+dx[i];
      int nby=by-dy[i],nbx=bx-dx[i];
      if(!inField(nay,nax))nay=ay,nax=ax;
      if(!inField(nby,nbx))nby=by,nbx=bx;
      if(visited[nay][nax][nby][nbx])continue;
      visited[nay][nax][nby][nbx]=true;
      Q.push( (state){nay,nax,nby,nbx,now.cnt+1} );
    }
  }
  cout<<"NA"<<endl;
}

int main(){
  while(1){
    cin>>W>>H;
    if(W==0&&H==0)break;
    state s;
    cin>>s.ax>>s.ay>>s.bx>>s.by;
    s.ay--,s.ax--,s.by--,s.bx--;
    s.cnt=0;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
	cin>>t[i][j];
	for(int k=0;k<H;k++){
	  for(int l=0;l<W;l++){
	    visited[i][j][k][l]=false;
	  }
	}
      }
    }
    solve(s);
  }
}

Measured memory_bytes: 25964
#include <stdio.h>

int main(){
	int a[5],i,j,tmp;
	scanf("%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4]);
	for (i = 0;i < 4;i++){
		for (j = 4;j > i;j--){
			if(a[j-1] < a[j]){
				tmp = a[j];
				a[j] = a[j-1];
				a[j-1] = tmp;;
			}
		}
	}
	printf("%d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4]);
	return 0;
}

Measured memory_bytes: 0
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.container;
import std.random;
  
void main() {
  readln.chomp.split.map!(to!int).array.sort.map!(to!string).join(" ").writeln;
}

Measured memory_bytes: 1072
#include<iostream>
using namespace std;
int main(void){
  long long int d ,n, cnt=0, tmp;
  cin >> d >> n;
  if(d==0) {
    if(n==100) cout << 101 << endl;
    else cout << n << endl;
  }
  if(d==1) {
    if(n==100) cout << 10100 << endl;
    else cout << 100 * n << endl;
  }
  if(d==2) {
    if(n==100) cout << 10000 * 101;
    else cout << 10000 * n << endl;
  }
}

Measured memory_bytes: 256
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n,m,Q;
int f[N],fa[N];

inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
inline void merge(int x,int y) {
    x=find(x),y=find(y);
    if (x!=y) fa[x]=y;
}

struct Edge { int u,v,w; } e[N];
bool operator <(Edge a,Edge b) { return a.w<b.w; }

int main() {
    n=read(),Q=read();
    memset(f,0x3f,sizeof(f));
    for (re int i=1;i<=Q;++i) {
        int a=read()+1,b=read()+1,c=read();
        chkmin(f[a%n+1],c+1),chkmin(f[b%n+1],c+2);
        e[++m]=(Edge){a,b,c};
    }
    int pos=1;
    for (re int i=2;i<=n;++i) if (f[i]<f[pos]) pos=i;
    for (re int i=pos%n+1,j=pos;i!=pos;j=i,i=i%n+1) chkmin(f[i],f[j]+2);
    for (re int i=1;i<n;++i) e[++m]=(Edge){i,i+1,f[i+1]};
    e[++m]=(Edge){n,1,f[1]};
    sort(e+1,e+m+1);
    for (re int i=1;i<=n;++i) fa[i]=i;
    int tot=0; ll ans=0;
    for (re int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (find(u)==find(v)) continue;
        ++tot,ans+=w,merge(u,v);
        if (tot==n-1) break;
    }
    printf("%lld\n",ans);
    return 0;
}
//qwqwq

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

int fld[8][8];

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

void dfs(int y,int x){
    fld[y][x]=0;
    for(int i=0;i<4;i++){
        for(int k=1;k<=3;k++){
            int ny=y+dy[i]*k;
            int nx=x+dx[i]*k;
            if(ny<0||ny>=8||nx<0||nx>=8||fld[ny][nx]==0)continue;
            dfs(ny,nx);
        }
    }
}

void solve(int C){
    for(int i=0;i<8;i++){
        char str[10];
        cin>>str;
        for(int j=0;j<8;j++){
            fld[i][j]=str[j]-'0';
        }
    }

    int sy,sx;
    cin>>sx>>sy;
    sx--;sy--;
    dfs(sy,sx);

    printf("Data %d:\n",C+1);
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            printf("%d",fld[i][j]);
        }
        puts("");
    }
}

int main(){
    int T;
    cin>>T;
    for(int i=0;i<T;i++)solve(i);
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <stdio.h>
// #define scanf " %s codekaze quiz"

using namespace std;
int main()
{   int n,k;
    long x;
    cin>>k>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int gap1=0;int house = 0;
    for(int i=0;i<n-1;i++){
        if(gap1<(arr[i+1]-arr[i])){
            gap1 = arr[i+1]-arr[i];
            house = i;
        }
    }
    int gap2 = k-arr[n-1] + arr[0];

    if(gap1>gap2){
       cout<< k-gap1;
    }
    else{
        cout << arr[n-1]-arr[0];
    }
    // cout<< k-min(gap1,gap2);
   
    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class A
{
	public static void Main() => (new Solver()).Solve();
}


public class Solver
{
	public void Solve()
	{
		string S = GetString();
		string T = GetString();
		WriteLine(T + S);
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 11092
def shuffle(cards, h):
    ret = ""
    for i in h:
        cards = cards[i:] + cards[:i]
    for c in cards:
        ret += c
    return ret

if __name__ == '__main__':
    retcards = []
    while True:
        str = input()
        if str == "-":
            break
        cards = list(str)
        m = int(input())
        h = []
        for i in range(m):
            n = int(input())
            h.append(n)
        retcard = shuffle(cards, h)
        retcards.append(retcard)
    for r in retcards:
        print(r)


Measured memory_bytes: 5604
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

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;
}

vector<vector<int>> edges;

// people[i] is a group number for i (or -1 if not assigned yet)
vector<int> people;

void dfs(const int cur_person, const int cur_group) {
    people[cur_person] = cur_group;
    for (auto next_person : edges[cur_person]) {
        if (people[next_person] == -1) {
            dfs(next_person, cur_group);
        }
    }
}

int main(void) {
    int N, M;
    cin >> N >> M;

    edges.resize(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    people.resize(N, -1);

    int group_no = 0;
    for (int i = 0; i < N; i++) {
        if (people[i] == -1) {
            dfs(i, group_no);
            group_no++;
        }
    }

    vector<int> group_number(group_no, 0);
    for (int i = 0; i < N; i++) {
        group_number[people[i]]++;
    }
    int ans = 0;
    for (int i = 0; i < group_no; i++) {
        chmax(ans, group_number[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 21016
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){

    int n; cin >> n;

    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        ans += r-l+1;
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int a[200005],dp[200005];
int minn(int x);
int k,n;
int min(int x)
{
	int small=minn(x-1)+ abs(a[x]-a[x-1]);
	//printf("first small is %d\n",small);
	for(int i=2; i<=k; i++)
		{

			if(small>minn(x-i)+abs(a[x]-a[x-i]))
				small=minn(x-i)+abs(a[x]-a[x-i]);
			//if(x==n)
			//	printf("for k = %d small is %d\n", i, minn(x-k)+abs(a[x]-a[x-k]));
		}
	return small;
}

int minn(int x)
{
	if(x<=k)
		return dp[x]=abs(a[x]-a[1]);

	else if(dp[x]!=-1)
		return dp[x];

		dp[x]=min(x);
		return dp[x];
}
int main()
{
	//int n;
	scanf("%d %d",&n,&k);

	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);

	for(int i=0; i<=n; i++)
		dp[i]=-1;

	//

	printf("%d", minn(n));
//	for(int i=1; i<=n; i++)
//		printf("%d ",dp[i]);
//	printf("\nmin for posn is %d", minn(n-2)+abs(a[n]-a[n-2]));
}

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

int main(){
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s.at(i);

    int ac = 0;
    int wa = 0;
    int tle = 0;
    int re = 0;

    for (int i = 0; i < n; i++){
        if (s.at(i) == "AC") ac++;
        if (s.at(i) == "WA") wa++;
        if (s.at(i) == "TLE") tle++;
        if (s.at(i) == "RE") re++;
    }

    cout << "AC" << " " << "x" << " " << ac << endl;
    cout << "WA" << " " << "x" << " " << wa << endl;
    cout << "TLE" << " " << "x" << " " << tle << endl;
    cout << "RE" << " " << "x" << " " << re << endl;

}

Measured memory_bytes: 6360
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}

const ll sz=10;

int main(){
  ll M;
  string C;
  cin>>M>>C;
  ll N=C.size();
  if(N==1){
    if(M>=10){cout<<-1<<endl;}
    else{cout<<M<<endl;}
    exit(0);
  }
  reverse(C.begin(),C.end());
  for(auto &I:C){I-='0';}
  vector<ll> cnt(sz,0);
  vector<ll> dp(N,1);
  for(int i=1;i<N;i++){dp[i]=(dp[i-1]*10LL)%MOD;}
  for(int i=0;i<N;i++){
    assert(C[i]>=0 && C[i]<sz);
    cnt[C[i]]+=dp[i];
    cnt[C[i]]%=MOD;
  }
  vector<ll> A(sz);
  for(int i=0;i<sz;i++){A[i]=i;}
  do{
    if(A[C[N-1]]!=0){
      ll sum=0;
      for(int i=0;i<sz;i++){
        sum+=(A[i]*cnt[i])%MOD;
        sum%=MOD;
      }
      sum%=MOD;
      if(sum<0){sum+=MOD;}
      if(sum==M){
        for(auto &I:C){
          char x=A[I]+'0';
          I=x;
        }
        reverse(C.begin(),C.end());
        assert(C[0]!='0');
        cout<<C<<endl;
        exit(0);
      }
    }
  }while(next_permutation(A.begin(),A.end()));
  cout<<"-1"<<endl;
  return 0;
}



Measured memory_bytes: 4172
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int( 1e3 +5)




int main(){
    int n,m;
    cin >> n >> m;
    int A[MAX],B[MAX];
    REP(i,n) scanf("%d",&A[i]);
    int check[MAX * MAX] = {};
    bool flag = false;
    REP(i,n){
        check[A[i]] ++;
        if(check[A[i]] == 2){
            flag = true;
            break;
        }
    }
    int che[MAX * MAX] = {};
    REP(i,m) scanf("%d",&B[i]);
    REP(i,m){
        che[B[i]] ++;
        if(che[B[i]] == 2){
            flag = true;
            break;
        } 
    }
    if(flag){
        cout << 0 << endl;
        return 0;
    }
    sort(A,A+n);
    sort(B,B+m);
    reverse(A,A+n);
    reverse(B,B+m);
    
    int aind = 0,bind = 0;
    int gyou=0,retu = 0;
    llong ans = 1;
    REPR(i,n * m){
        if(i ==0) break;
        if(A[aind] == i and B[bind] == i){
            gyou ++;
            retu ++;
            aind ++;
            bind ++;
        }
        else if(A[aind] !=i and B[bind] ==i){
            ans *= gyou ;
            ans %=MOD;
            retu ++;
            bind ++;
        }
        else if(A[aind] == i and B[bind] !=i){
            ans *= retu ;
            ans %= MOD;
            gyou ++;
            aind ++;
        }
        else{
            ans *= gyou * retu - (n*m - i);
            ans %= MOD;
        }
        if(ans ==0) break;
    }
    if(gyou != n or retu !=m){
        cout << 0 << endl;
        return 0;
    }
    cout << ans << endl;
}

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

int main() {
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int k,p;
		cin>>k>>p;
		if(k<p){
			cout<<k<<endl;
		}else{
			int ans;
			ans=k%p;
			if(ans==0){
				cout<<p<<endl;
			}else{
				cout<<ans<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll X,Y;

int main(){
  cin >> X >> Y;
  bool alc = true;
  if(X <= 1 && Y <= 1){
    alc = false;
  }else{
    if(abs(X-Y) <= 1){
      alc = false;
    }else{
      alc = true;
    }
  }

  cout << (alc ? "Alice" : "Brown") << endl;

  return 0;
}


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

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int v[100005];
pii o[100005];
pii e[100005];

int main()
{
	int n;
	cin >> n;
	REP(i, n)
	{
		cin >> v[i];
	}

	REP(i, n)
	{
		if (i % 2 == 0)
		{
			e[v[i]].first++;
			e[v[i]].second = v[i];
		}
		else
		{
			o[v[i]].first++;
			o[v[i]].second = v[i];
		}
	}
	sort(e, e + 100005, [](pii a, pii b) {return a.first > b.first; });
	sort(o, o + 100005, [](pii a, pii b) {return a.first > b.first; });
	
	int sum = 0;
	if (e[0].second != o[0].second)
	{
		FOR(i, 100005, 1)
		{
			sum += e[i].first;
			sum += o[i].first;
		}
	}
	else
	{
		int sum_o = o[0].first;
		FOR(i, 100005, 2)
		{
			sum_o += o[i].first;
		}
		int sum_e = e[0].first;
		FOR(i, 100005, 2)
		{
			sum_e += e[i].first;
		}
		int sumo2 = 0;
		int sume2 = 0;
		FOR(i, 100005,1)
		{
			sumo2 += o[i].first;
			sume2 += e[i].first;
		}
		sum = std::min(sumo2 + sum_e, sume2 + sum_o);

	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 2176
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let mut s=0;
    let mut m=0;
    for _ in 0..read::<i32>(){
        let l=read::<i32>();
        if m<l{m=l}
        s+=l
    }
    println!("{}",if s>m*2{"Yes"}else{"No"})
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define Yes(n) cout << ((n) ? "YES" : "NO") << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V))

//vector<string> split(string,string);

//template<typename T>
//void swap(T*,T*);
//char ToUpper (char cX) { return toupper(cX); }

int main()
{
    int a,b;
    cin >> a >> b;
    cout << (a + b < 24 ? a + b : a + b -24);
}

Measured memory_bytes: 256
function mod(n, m) {
    return ((n % m) + m) % m;
}

const processData = (lines) => {
    const nums = lines[1].split(' ').map(x => BigInt(+x))
    const limit = BigInt(Math.pow(10, 9) + 7)
    let sum = BigInt(0)
    let totalSum = BigInt(0)
    for (let i=0; i<nums.length; i++) {
        totalSum = (totalSum + nums[i]) % limit
    }
    totalSum = totalSum % limit
    let localSum = totalSum
    for (let i=0; i<nums.length-1; i++) {
        localSum = mod(localSum - nums[i], limit)
        sum = (sum + ((nums[i] * localSum)%limit)) % limit
    }

    console.log(sum.toString(10))
}

let i = ''
process.stdin.on('data', c => i += c)
process.stdin.on('end', () => {
    const {EOL} = require('os')
    const lines = i.split(EOL) /*your input text, split by lines*/
    processData(lines)
})


Measured memory_bytes: 81896
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <bitset>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

ll xyz[1010][3];


int
main(void){  
  int n, m;
  cin >> n >> m;

  ll ans=0;

  REP(i, n) REP(j, 3) cin >> xyz[i][j];
  
  // 001 ... xy -z
  REP(bit, (1<<3)){
    vector<ll> v;    
    REP(i, n){
      ll tmp = 0;      
      REP(j, 3){
	if(bit & (1<<j)) tmp -= xyz[i][j];       
	else tmp += xyz[i][j];	
	//cout << bitset<3>(bit) << " i: " << i << " j:" << j << " sum:" << tmp << endl; 	
      }
      v.push_back(tmp);
    }
    sort(v.begin(), v.end(), greater<ll>());
    ll res = 0;
    REP(i, m) res += v[i];    
    ans = max(ans, res);
  }
  cout << ans << endl;  
  return 0;
}


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

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

        if (s.contains("AC"))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 35564
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>>vvi;

int main(){
  int n;string s;
  cin>>n>>s;
  int count=0;
  int MAX=0;
  for(int i=0;i<n;i++){
    
    if(s[i]=='I')count++;
    else count--;
    MAX=max(MAX,count);
  }
  cout<<MAX<<endl;
}

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

int main(){
	int n, t;
	cin >> n >> t;
	int mini = 1e9, diff = -1e9, count = 0;
	while(n--){
		int a;
		cin >> a;
		mini = min(mini, a);
		if(diff == a - mini) count++;
		if(diff < a - mini){
			diff = a - mini;
			count = 1;
		}
	}
	cout << count << endl;
}

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

int main(){
    int n;
    int a[128];
    int b[128];
    string ans="";
    rep(i,128) a[i]=0;
    cin>>n;
    rep(i,n){
        string s;
        cin>>s;
        int ss=s.size();
        rep(j,128) b[j]=0;
        rep(j,ss){
            if(i==0){
                a[s[j]]++;
            }else{
                b[s[j]]++;
            }
        }
        for(char j='a';j<='z';j++){
            if(i!=0){
                a[j]=min(a[j],b[j]);
            }
        }
    }
    for(char i='a';i<='z';i++){
        rep(j,a[i]){
            ans.push_back(i);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define X first
#define Y second
#define WIDTH 8
#define HEIGHT 8

using namespace std;

vector<string> init(){
	vector<string> map;
	for(int i = 0; i < HEIGHT; i++){
		string tmp;
		getline(cin,tmp);
		map.push_back(tmp);
	}
	return map;
}

void countNum(vector<string> map, int *count){
	int counter = -1;
	
	for(int i = 0; i < HEIGHT; i++){
		for(int j = 0; j < WIDTH ; j++){
			if(map[i][j] == '1'){
				counter++;
				if(counter == 3) return;
			}
			else{
				if(counter >= 0) count[counter]++;
			}
		}
	}

	return;
}


char checkChar(int *count){
	if(count[0] == 0 && count[1] == 6 && count[2] == 0){
		return 'A';
	}
	else if(count[0] == 7 && count[1] == 7 && count[2] == 7){
		return 'B';
	}
	else if(count[0] == 0 && count[1] == 0 && count[2] == 0){
		return 'C';
	}
	else if(count[0] == 6 && count[1] == 0 && count[2] == 6){
		return 'D';
	}
	else if(count[0] == 0 && count[1] == 7 && count[2] == 0){
		return 'E';
	}
	else if(count[0] == 7 && count[1] == 0 && count[2] == 7){
		return 'F';
	}
	else if(count[0] == 0 && count[1] == 5 && count[2] == 0){
		return 'G';
	}
}



int main(){
	
	while(1){
		if(cin.eof()) break;
		vector<string> map = init();
		int count[] = {0, 0, 0};
		countNum(map, count);
		cout << checkChar(count) << endl;
		//入力で一行改行が入ってしまうのでそれ対策
		string tmp;
		getline(cin, tmp);
	}
	return 0;
}

Measured memory_bytes: 1176
N, M, K = map(int, input().split())
def check():
    for i in range(M):
        P = M-2*i
        K1 = K - i*N
        if P==0:
            if K1 == 0:
                return True
            return False
        if K1%P==0 and K1//P<=N and K1//P>=0:
            return True
    return False
if check():
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
using namespace std;
 
struct odd : public unary_function<int, bool> { bool operator () (int x) const { return (x % 2) != 0; } };
void dis(int *Array, int N) { for(int i = 0; i < N; ++i) {std::cout.width(1); std::cout << Array[i];} std::cout << std::endl;}
signed fac(int n){return (n==1 || n==0) ? 1: n * fac(n - 1);}
bool V(char x) {return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u'); } 
template<typename T, typename U> inline signed  amin(T &x, U y) { if(y < x) x = y; return x;}
template<typename T, typename U> inline signed  amax(T &x, U y) { if(x < y) x = y; return x;}
//signed m(){long long T, pp,p,ppp, ct, nn, xx; cin >> p; cin.ignore(); for(int k=0;k<n;k++){for(int l=0;l<(k+1);l++){cin>>a[k][l];}}
#define inn freopen("input.txt", "r", stdin) 
#define outt freopen("output.txt", "w",stdout)
#define all(cont) cont.begin(), cont.end()
#define ll          long long
#define sz(x)       (int)x.size()
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
 
ll n,E,E1,D=0,c,m,D1,k=0,arr[1000],a,b,d,e,f,flag=0,max2=0,l=0;
 
vector<int>fi,fi1;
string s;
std::vector<int>::iterator low1, low2;
//set <char> se;
 
int main () {
double max1=0,st;
cin>>n;
for(int i=1; i<=n; i++)
{
    if(i%2!=0)
    {
        max1++;
    }
}
st=max1/n;
cout<<st;
 
    
 
 
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rep(i, k, n) for (int i = (int)(k); i < (int)(n); ++i)
#define rrep(i, k, n) for (int i = (int)(n) - 1; i >= (int)(k); --i)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vv_ii;
typedef pair<int,ii> i_ii;
typedef vector<i_ii> vi_ii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template <class T>
inline ostream& operator<<(ostream & o, vector<T> const& v) {
    for (int i = 0; i < (int)(v.size()) - 1; ++i)
        o << v[i] << ' ';
    if (!v.empty())
        o << v.back();
    return o;
}

template <class T, class Q>
inline ostream& operator<<(ostream & o, pair<T,Q> const& p) {
    o << "(" << p.fi << "," << p.se << ")";
    return o;
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    char a, b;
    cin >> a >> b;
    string sa(a - '0', b), sb(b - '0', a);
    //cerr << "sa -> " << sa << " sb -> " << sb << endl;
    ll ia = stoll(sa), ib = stoll(sb);
    cout << max(ia, ib) << '\n';


    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

n = int(input())
a = 0
if n <= 111:
    a = 111
elif n <= 222:
    a = 222
elif n <= 333:
    a = 333
elif n <= 444:
    a = 444
elif n <= 555:
    a = 555
elif n <= 666:
    a = 666
elif n <= 777:
    a = 777
elif n <= 888:
    a = 888
elif n <= 999:
    a = 999
print(a)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define M 1000010

int main(){
	IOS;
	ll r;cin>>r;
	cout<<(r*r);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <unordered_map>
#include <array>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <random>
#include <numeric>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;

const int MAX_N = 100000;
int N;
int A[MAX_N];

int main() {
  cin >> N;
  rep(i, N) cin >> A[i];

  int count = 0;
  for (int i = 0; i < N; ++i) {
    if (A[i]%2 == 1) ++count;
  }

  if (count%2 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 640
using System;
using System.Linq;
using System.Collections.Generic;

class Bmondai {
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        decimal ans = 0;
        for (int i=0;i<N;++i)
        {
            var xu = Console.ReadLine().Split(' ').ToArray();
            var x = decimal.Parse(xu[0]);
            if (xu[1] == "JPY") ans += x;
            else ans += x * 380000;
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define err(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

typedef long long ll;

map<int, int> cnt;

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	
	for (int i = 0; i < n; i++) cin >> A[i];
	sort(A.begin(), A.end());
	
	vector<int> p;
	int ind = -1;
	
	for (int i = 0; i < n; i++) {
		int cur = ++cnt[A[i]];
		if (cur == 4) ind = i;
		if (cur == 2) p.push_back(A[i]);
	}
	
	ll ans = 0;
	if (ind != -1) ans = max(ans, 1ll * A[ind] * A[ind]);
	if (p.size() > 1) ans = max(ans, 1ll * p.back() * p[(int)p.size() - 2]);
	cout << ans << "\n";
	
	return 0;
}

Measured memory_bytes: 5376
N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = [0 for i in range(M)]
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
distance = [-10**20 for i in range(N)]
distance[0] = 0
for i in range(1,N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
negative = [False for i in range(N)]
for i in range(N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
            negative[v] = True
        if negative[u]:
            negative[v] = True
if negative[N-1]:
    print("inf")
else:
    print(distance[N-1])


Measured memory_bytes: 46296
#include <stdio.h>
int main(void)
{
    char s[5];

scanf("%s", s);

 if(s[0]==s[1] || s[1]==s[2] || s[2]==s[3]){
        printf("Bad\n");
    }else{
        printf("Good\n");
    }

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
// cout << "\t" << endl;

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a;
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    a.push_back(tmp);
  }

  int dmax = 0;
  int didx = 0;
  for (int i = 0; i < n - 1; i++) {
    if (a.at(i + 1) - a.at(i) > dmax) {
      dmax = a.at(i + 1) - a.at(i);
      didx = i;
    }
  }
  if (k - a.at(n - 1) + a.at(0) > dmax) {
    dmax = k - a.at(n - 1) + a.at(0);
    didx = 0;
  }

  int ans = k - dmax;
  cout << ans << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int N;
vector<int> L;

int main(void){
	//IO("test.in", "test.out");
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		int s;
		scanf("%d", &s);
		L.push_back(s);
	}
	for(int i = 0; i < L.size() - 1; i++)
		for(int j = L.size() - 1; j > i; j--)
			if(L[i] == L[j]) L.erase(L.begin() + j);
	printf("%d\n", L.size());
}

Measured memory_bytes: 256
# エラトステネスの篩, 累積和
from math import sqrt

N = 10 ** 5

p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)
for j in range(4, N + 1, 2):
  p[j] = False
for i in range(3, n + 1, 2):
  if p[i]:
    for j in range(i + i, N + 1, i):
      p[j] = False

cs = [0] * (N + 1)
for i in range(3, N + 1, 2):
  if p[i] and p[(i + 1) // 2]:
    cs[i] = 1
for i in range(1, N + 1):
  cs[i] += cs[i - 1]

Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(cs[r] - cs[l - 1])


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

typedef struct edge{
    int x;
    struct edge* next;
}edge;

typedef struct node{
    long long int value;
    edge* fst;
    edge* lst;
}node;

void init(node* p){
    p->value = 0;
    p->fst = NULL;
    p->lst = NULL;
}

void add(node* p, int x){
    if(p->fst == NULL){
        p->fst = (edge*)malloc(sizeof(edge));
        p->lst = p->fst;
    }else{
        p->lst->next = (edge*)malloc(sizeof(edge));
        p->lst = p->lst->next;
    }
    p->lst->x = x;
    p->lst->next = NULL;
}

void func(node* a, int x, int pre){
    long long int v = (a+x)->value;
    edge* t = (a+x)->fst;
    while(t != NULL){
        if(t->x != pre){
            (a+(t->x))->value += v;
            func(a, t->x, x);
        }
        t = t->next;
    }
}

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    int a[n-1], b[n-1], p[q], x[q];
    for(int i=0; i<n-1; i++){
        scanf("%d %d", &a[i], &b[i]);
    }
    for(int i=0; i<q; i++){
        scanf("%d %d", &p[i], &x[i]);
    }
    node ans[n+1];
    for(int i=1; i<=n; i++){
        init(&ans[i]);
    }
    for(int i=0; i<n-1; i++){
        add(&ans[a[i]], b[i]);
        add(&ans[b[i]], a[i]);
    }
    for(int i=0; i<q; i++){
        ans[p[i]].value += x[i];
    }
    func(ans, 1, -1);
    for(int i=1; i<=n; i++){
        printf("%lld ", ans[i].value);
    }

    return 0;
}

Measured memory_bytes: 32000
def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * n for i in range(n)]
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for i in range(2, n):
        for l in range(n - i):
            r = i + l
            res = 0
            if abs(a[l] - a[r]) <= 1:
                if dp[l + 1][r - 1] == r - l - 1:
                    dp[l][r] = r - l + 1
                    continue
            res = dp[l + 1][r - 1]
            for li in range(l + 1, r):
                tmp = dp[l][li] + dp[li + 1][r]
                if res < tmp:
                    res = tmp
            dp[l][r] = res
    print(dp[0][n-1])
    def dfs(l, r):
        if l >= r: return 0
        if dp[l][r] != -1: return dp[l][r]
        if abs(a[l] - a[r]) <= 1:
            if dfs(l + 1, r - 1) == r - l - 1:
                dp[l][r] = r - l + 1
                return r - l + 1
        res = 0
        for li in range(l + 1, r):
            tmp = 0
            f = 0
            if dp[l][li] != -1:
                tmp += dp[l][li]
            else:
                tmp += dfs(l, li)
            if dp[li + 1][r] != -1:
                tmp += dp[li + 1][r]
            else:
                tmp += dfs(li + 1, r)
            if res < tmp:
                res = tmp
        dp[l][r] = res
        return res
    # print(dfs(0, n - 1))


if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break



Measured memory_bytes: 16508
#include <iostream>
using namespace std;
int x,b,p,ans;
int sqt(int y,int z){
	int d=1;
	for(int i=0;i<z;i++){
		d=d*y;
	}
	return d;
}
int main(){
	cin>>x;
	if(x<=3){
		cout<<1;
	}else{
		for(b=2;b*b<=x;b++){
		for(p=2;;p++){
			if(sqt(b,p)<=x&&sqt(b,p)>ans) ans=sqt(b,p);
			if(sqt(b,p)>x) break;
		}
	}
	cout<<ans;
	}
	
	return 0;
}

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

int main(){
	vector<int> a(3);
	for(int i=0;i<3;i++)cin>>a[i];
	sort(a.begin(),a.end());
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
}


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

import numpy as np

N, M = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(N)]

E = np.array(e)
E = E[E[:,0].argsort()]

drink = 0
money = 0
for m, i in E:
    drink += i
    money += m*i
    if drink > M:
        break

yobun = drink - M
money -= yobun * m

print(money)

Measured memory_bytes: 34056
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
//int csp=1e-10;
int a[200010]; 
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int l=-1e18,r=1e18;
	while(l+1!=r){
		//cout<<1<<endl; 
		int mid=(l+r)/2;
		int cnt=0;
		for(int i=0;i<n;i++){
			if(a[i]<0){
				int l1=i,r1=n;
				while(l1+1!=r1){
					int mmid=(l1+r1)/2;
					if(a[i]*a[mmid]<=mid) r1=mmid;
					else l1=mmid; 
				}//这里的二分r是找的有多少个大于mid 
				cnt+=n-r1;//这里就是有多少个小于的了 
				//cout<<1<<endl;
			}
			else{
				int l1=i,r1=n;
				while(l1+1!=r1){
					int mmid=(l1+r1)/2;
					if(a[i]*a[mmid]<=mid) l1=mmid;
					else r1=mmid;
				}//l1是有少小于，但是要减去i之前的 
				cnt+=l1-i;
			}
		//	cout<<cnt<<endl;
		}
	//	cout<<cnt<<endl;
		if(cnt<k) l=mid;
		else r=mid;
	}
	cout<<r<<endl;
    return 0;
}


Measured memory_bytes: 1792
from collections import Counter
import copy
from itertools import combinations


def A(s):
  if s == 'RRR':
    return 3
  elif s == 'RRS':
    return 2
  elif s == 'RSR':
    return 1
  elif s == 'SRR':
    return 2
  elif s == 'RSS':
    return 1
  elif s == 'SRS':
    return 1
  elif s == 'SSR':
    return 1
  elif s == 'SSS':
    return 0
  l = 0
  max_l = 0
  for i in range(len(s)):
    if i == 0 and s[i] == 'R':
      l += 1
    elif s[i - 1] == s[i] and s[i] == 'R':
      l += 1
    else:
      l = 0
    if l > max_l:
      max_l = l
  return max_l


def B():
  pass


def C():
  pass


def main():
  s = input()
  print(A(s))


if __name__ == '__main__':
  main()


Measured memory_bytes: 9536
import heapq
INF = 10**15

n, m, s, t = [int(item) for item in input().split()]
yen = [[] for _ in range(n)]
snk = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist

for i in range(m):
    u, v, a, b = [int(item) for item in input().split()]
    u-=1; v-=1
    yen[u].append([v, a])
    yen[v].append([u, a])
    snk[u].append([v, b])
    snk[v].append([u, b])

yen_dijk = Dijkstra(yen)
snk_dijk = Dijkstra(snk)

yen_dist = yen_dijk.calc(s-1)
snk_dist = snk_dijk.calc(t-1)
 
ans = [0] * n
min_cost = 10**15
i = n-1
for yy, ss in zip(yen_dist[::-1], snk_dist[::-1]):
    min_cost = min(min_cost, yy + ss)
    ans[i] = min_cost
    i -= 1

for item in ans:
    print(10**15 - item)

Measured memory_bytes: 127392
import java.util.*;
public class Main {
	
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		int E = sc.nextInt();
		int F = sc.nextInt();
		
		
		int maxWater = 0;
		int maxSugar = 0;
		float maxConcentration = 0;
		for (int a = 0; a <= F/100; a+=A) {
			for (int b = 0; b <= F/100-a; b+=B) {
				float water = a*100+b*100;
				for (int c = 0; c <= F-water; c+=C) {
					for (int d = 0; d <= F-water-c; d+=D) {
						int sugar = c + d;
						
						if (water == 0)
							continue;
						
						if (water/100 * E < sugar)
							continue;
						
						if (water + sugar > F)
							continue;
						
						if ((float)((sugar * 100) / (water + sugar)) >= maxConcentration) {
							maxConcentration = (float)((sugar * 100) / (water + sugar));
							maxWater = (int) water;
							maxSugar = sugar;
						}
					}
				}
			}
		}
		
		System.out.println(maxWater+maxSugar + " " + maxSugar);
		
	}
	
}


Measured memory_bytes: 21844
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, K = map(int, raw_input().split())
DP = [[0] * (K + 1) for i in range(K + 1)]
bias = 0

for i in range(N):
    x, y, c = raw_input().split()
    x, y, c = int(x), int(y), (c == 'W')
    p = (x / K + y / K + c) % 2
    DP[y % K + 1][x % K + 1] += 1 - 2 * p
    bias += p

for i in range(K):
    for j in range(K + 1):
        DP[i + 1][j] += DP[i][j]

for i in range(K + 1):
    for j in range(K):
        DP[i][j + 1] += DP[i][j]

ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        S1 = DP[i][j] * 2 - DP[i][K] - DP[K][j] + DP[K][K]
        S2 = DP[i][K] + DP[K][j] - DP[i][j] * 2
        ans = max(ans, S1, S2)

print ans + bias

Measured memory_bytes: 23272
from collections import defaultdict
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

count = defaultdict(int)
for a in A:
    count[a] += 1

combi = defaultdict(int)
for a in count:
    combi[a] = comb(count[a],2)

total = sum(list(combi.values()))
for i in range(n):
    print(total - (count[A[i]] - 1))

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

sA = sum(A)

div_list = []

for i in range(1,int(sA**0.5)+1):
    if sA%i==0:
        if i!=sA**0.5:
            div_list.append(i)
            div_list.append(sA//i)
        else:
            div_list.append(i)


div_list.sort(reverse=True)

for d in div_list:
    count=0
    count_list = []
    l = 0
    for a in A:
        n=a%d
        if n!=0:
            l+=1
            count+=n
            count_list.append(n)

    if count%d==0:
        if count//d<l:
            count_list.sort()
            if sum(count_list[:l-count//d])<=K:
                break

print(d)

Measured memory_bytes: 41564
N=int(input())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])

min_b=10**9
max_a=0
min_a=10**9

for i in range(N):
    min_b=min(min_b,L[i][1])
    max_a=max(max_a,L[i][0])
    min_a=min(min_a,L[i][0])

# ans=(min_a-1)+(max_a-min_a+1)+min_b
ans = max_a + min_b

print(ans)


Measured memory_bytes: 19616