akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
using namespace std;

int main() {

	long N, K, Q;
	cin >> N >> K >> Q;

	vector<long> A(N, 0);
	long ival = 0;
	for (long i = 0; i < Q; i++) {
		cin >> ival;
		A[ival - 1] += 1;
	}

	long diff = K - Q;

	vector<string> ans(N, "Yes");

	if (diff <= 0) {
		diff = (long)abs(diff);
		for (long i = 0; i < N; i++) {
			if (A[i] <= diff) {
				ans[i] = "No";
			}
			cout << ans[i] << endl;
		}
	}
	else {
		for (long i = 0; i < N; i++) {
			cout << ans[i] << endl;
		}
	}

	return 0;
}



Measured memory_bytes: 6784
#include <bits/stdc++.h>
typedef long long ll;
int mod = 1000000007;
using namespace std;
int main()
{
    string str1,str2,str3;
    int a,b;
    while(cin>>str1>>str2>>a>>b>>str3)
    {
       if(  str1==str3 ) {  cout<<a-1<<' '<<b<<endl; }
       else { cout<<a<<' '<<b-1<<endl; }
    }
     
   return 0;   
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*; 
 
class Main { 
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
      	//int x = sc.nextInt();
      	//int t = sc.nextInt();
      	PrintWriter out = new PrintWriter(System.out);
        out.println(Math.max(sc.nextInt() - sc.nextInt(), 0));
      	out.flush();
    }

static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}

    public int nextInt() {
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
}


}



Measured memory_bytes: 21332
def main():
    n = int(input())
    a = list(map(int, input().split()))

    pos = True
    num_dict = {}
    if n % 2 == 0:
        for i in range(n):
            if a[i] % 2 == 0:
                pos = False
                break

            num_dict[a[i]] = num_dict.get(a[i], 0) + 1

    else:
        cnt0 = 0
        for i in range(n):
            if a[i] % 2 == 1:
                pos = False
                break
            elif a[i] == 0:
                cnt0 += 1
            else:
                num_dict[a[i]] = num_dict.get(a[i], 0) + 1

        if cnt0 != 1:
            pos = False

    for i in num_dict:
        if num_dict[i] != 2:
            pos = False

    if pos:
        com = 1
        for i in range(len(num_dict)):
            com *= 2
            if com >= 10 ** 9 + 7:
                com %= 10 ** 9 + 7

        print(com)
    else:
        print(0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14436
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(vec) (vec).begin(), (vec).end()
#define SUM(...) accumulate(ALL(__VA_ARGS__),0LL)
#define DSUM(...) accumulate(ALL(__VA_ARGS__),0.0)
using namespace std;
using ll = long long;
using P = pair<int, int>;

// 便利関数
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

// 入出力
void print() { std::cout << '\n'; }
template <class T>void print(const T &x) {std::cout << x <<'\n';}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

// 初期時読み込み
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

const int INF = 2002002002;
const string YES = "Yes";
const string NO = "No";

void solve(long long a, long long b, long long c){
    vector<long long> n;
    n.push_back(a);
    n.push_back(b);
    n.push_back(c);
    sort(n.begin(), n.end());
    if (n[0] + n[1] == n[2]) print(YES);
    else print(NO);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    solve(a, b, c);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		long A = scn.nextLong(), B = scn.nextLong();

		long N = MyMath.gcd(A,B);
		int ans = 1;
		for(int i = 2;i <= Math.sqrt(N);i++) {
			if(N%i==0) {
				ans++;
				while(N%i==0) {
					N/=i;
				}
			}
		}
		if(N>1)ans++;
		System.out.println(ans);
	}
}
class MyMath{
	public static long gcd(long a,long b) {
		while(a%b!=0) {
			long buf = a%b;
			a = b;
			b = buf;
		}
		return b;
	}}



Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	i64 n; scanf("%lld", &n);

	std::vector<i64> ans; ans.push_back(n);
	for(i64 i = 2; i * i <= n; i++) {
		if(n % i) continue;
		
		{
			i64 now = n, d = i;
			while(!(now % d)) now /= d;
			if(now % d == 1) ans.push_back(d);
		}
		{
			i64 now = n, d = n / i;
			while(!(now % d)) now /= d;
			if(now % d == 1) ans.push_back(d);
		}
	}

	for(i64 i = 1; i * i <= n - 1; i++) {
		if((n - 1) % i) continue;

		i64 d = i;
		if(std::__gcd(n, d) == 1 and n % d == 1) ans.push_back(d);

		d = (n - 1) / i;
		if(std::__gcd(n, d) == 1 and n % d == 1) ans.push_back(d);
	}
	
	sort(begin(ans), end(ans));
	ans.erase(unique(begin(ans), end(ans)), end(ans));
	printf("%d\n", ans.size());
	return 0;
}


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

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N;
int A[111111];

// 1-indexed
int l[111111]; // 左から累積
int r[111111]; // 右から累積

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

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

  for (int i = 0; i < N; i++) {
    l[i+1] = gcd(l[i], A[i]);
  }
  for (int i = N; i >= 1; i--) {
    r[i] = gcd(r[i+1], A[i-1]);
  }

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    int tmp = gcd(l[i-1], r[i+1]);
    chmax(ans, tmp);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2560
n = int(input())
a_li = []
b_li = []
for _ in range(n):
    a,b = map(int, input().split())
    a_li.append(a)
    b_li.append(b)

cnt = 0
for i in range(1,n+1):
    if (a_li[-i]+cnt) % b_li[-i] != 0:
        cnt += b_li[-i] - ((a_li[-i]+cnt) % b_li[-i])
print(cnt)


Measured memory_bytes: 11048
class segtree:
    ## define what you want to do ,(min, max)
    sta = -1
    func = max

    def __init__(self,n):
        self.n = n
        self.size = 1 << n.bit_length()
        self.tree = [self.sta]*(2*self.size)

    def build(self, list):
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

    def max_right(self, l, x):
        if l == self.n:
            return l
        l += self.size
        res = self.sta
        check = True
        while check or (l & -l) != l:
            check = False
            while l%2 == 0:
                l >>= 1
            if not self.func(res,self.tree[l]) < x:
                while l < self.size:
                    l <<= 1
                    if self.func(res,self.tree[l]) < x:
                        res = self.func(res,self.tree[l])
                        l += 1
                return l - self.size
            res = self.func(res,self.tree[l])
            l += 1
        return self.n

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

seg = segtree(n)
seg.build(a)
for _ in range(q):
    t,x,v = map(int,input().split())
    if t == 1:
        seg.set(x-1,v)
    elif t == 2:
        print(seg.get(x-1,v))
    else:
        print(seg.max_right(x-1,v)+1)

Measured memory_bytes: 31356
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    double rootN = Math.sqrt((double)N);
    int min = Integer.MAX_VALUE;
    for (int i = 1; i <= rootN; i++) {
      if (N % i != 0) {
        continue;
      }
      int tmp = Math.max(digitCount(i), digitCount(N / i));
      if (tmp < min) {
        min = tmp;
      }
    }
    System.out.println(min);
  }

  public static int digitCount(long n) {
    int count = 0;
    while (n > 0) {
      count++;
      n /= 10;
    }
    return count;
  }
}

Measured memory_bytes: 22736
#include <stdio.h>
#include <string.h>
 
#define M 1000999 
#define NIL (-1)
#define L 14
 
char H[M][L]; 

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

int getKey(char str[]){
  int sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}
 
int h1(int key) {
  return key % M;
}
int h2(int key){
  return 1 + key % (M-1);
}
 
int find(char s[]){
 
  int i = 0,num;
 
  while(1){
    num = (h1(getKey(s)) + i * h2(getKey(s))) % M;
 
    if(H[num][0] == '\0') return 0;    
 
    if(strcmp(H[num],s) == 0){
      return 1;
    }
  i++;
 
  }
 
}
 
void insert(char s[]){
 
  int i=0,num;
 
  while(1){
    num = (h1(getKey(s)) + i *h2(getKey(s))) % M;
     
    if(H[num][0] == '\0'){  
      strcpy(H[num],s);
      return;
    } 
    i++;
  }
   
}
 
 
int main(){
    int i, n, h;
    char s[L], cm[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    scanf("%d", &n);
    for ( i = 0; i < n; i++ ){
      scanf("%s %s", cm, s);
      if ( cm[0] == 'i' ){
          insert(s);
      } else {
          if (find(s)){
            printf("yes\n");
          } else {
          printf("no\n");
        }
      }
    }
    return 0;
}

Measured memory_bytes: 14292
class Restaurant():
    def __init__(self, i, s, p):
        self.i = i
        self.s = s
        self.p = p

    def __eq__(self, other):
        return (self.s == other.s) and (self.p == self.p)

    def __lt__(self, other):
        return (self.s < other.s) or (self.p > other.p and self.s == other.s)

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

N = int(input())
restaurants = []

for i in range(N):
    s, p = input().split()
    p = int(p)
    restaurants.append(Restaurant(i+1, s, p))

restaurants.sort()

for r in restaurants:
    print(r.i)


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

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

using namespace std;

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<int64_t> m(4001);
    vector<int> order;
    set<int> already;
    REP(i,n){
      int64_t no, p, num;
      cin>>no>>p>>num;
      if (!already.count(no)) {
        order.push_back(no);
        already.insert(no);
      }
      m[no] += p * num;
    }
    int cnt = 0;
    for(int no:order) {
      if (m[no] >= 1000000) {
        ++cnt;
        cout << no << endl;
      }
    }
    if (!cnt)
      cout << "NA" << endl;
  }
  return 0;
}

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

int main() {
  int length, buf;
  vector<int> input;
  cin >> length;
  for (int i = 0; i < length; i++) {
      cin >> buf;
      input.push_back(buf);
  }

    sort(input.begin(), input.end());
    int mid_key = input.size() / 2;
    cout << input[mid_key] - input[mid_key - 1] << endl;

  return 0;
}

Measured memory_bytes: 892
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long lli;
int main()
{
	int a, b;
    cin >> a >> b;
    if(b%a==0) {
        cout << a+b << endl;
    } else {
        cout << b-a << endl; 
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,i,j;
  cin >> n;
  vector<int>a(n);
  vector<int>ans(n+1,0);
  for(i=1; i<n; i++){
    cin >> a.at(i);
    ans.at(a.at(i))++;
  }
  for(i=1; i<=n; i++){
    cout << ans.at(i) << endl;
  }
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll A, B, C, D;
ll gcd(ll a, ll b) {
    if(a < b) swap(a, b);
    if(a % b == 0) return b;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}
ll f(ll in) {
    ll num = in;
    num -= in / C;
    num -= in / D;
    num += in / lcm(C, D);
    return num;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> B >> C >> D;
    cout << f(B) - f(A - 1) << endl;
    cerr << f(B) << " " << f(A - 1) << endl;
    return 0;
}


Measured memory_bytes: 256
x = int(input())
def sft(s):
  if int(s) > x:
    return 0
  if all(s.count(c) > 0 for c in '753'):
    ret = 1
  else:
    ret = 0
  for c in '753':
    ret += sft(s + c)
  return ret
print(sft('0'))

Measured memory_bytes: 2940
<?php

    fscanf(STDIN,"%d%d",$N,$K);
    
    $S = trim(fgets(STDIN));

    $Sarray = str_split($S);
    
    $Sarray[$K-1] = strtolower($Sarray[$K-1]);
    
    $S = implode("",$Sarray);
    
    echo $S;    

?>

Measured memory_bytes: 16244
import numpy as np
h, w, a, b = list(map(int, input().split()))
Ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if ( i < b and j >= a ) or ( i >= b and j < a) :
            Ans[i][j] = 1
for i in range(h):
    print(''.join(list(map(str, Ans[i]))))

Measured memory_bytes: 22152
using System;
using System.Collections.Generic;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		var hs=new Dictionary<char,int>();
		string s=Console.ReadLine();
		for(int i=0;i<s.Length;i++){
			if(hs.ContainsKey(s[i])){hs[s[i]]++;}
			else{hs.Add(s[i],1);}
		}
		for(int i=1;i<n;i++){
			s=Console.ReadLine();
			var q=new Dictionary<char,int>();
			for(int j=0;j<s.Length;j++){
				if(q.ContainsKey(s[j])){q[s[j]]++;}
				else{q.Add(s[j],1);}
			}
			List<char> kl=new List<char>(hs.Keys);
			foreach(char c in kl){
				if(!q.ContainsKey(c)){hs.Remove(c);}
				else if(hs[c]>q[c]){hs[c]=q[c];}
			}

		}
		List<char> li=new List<char>(hs.Keys);
		li.Sort();
		string ans="";
		foreach(char c in li){
			for(int i=0;i<hs[c];i++){ans+=c;}
		}
		Console.WriteLine("{0}",ans);
	}

}

Measured memory_bytes: 13408
n, k = gets.chomp.split.map(&:to_i)

arr = Array.new(n+1, 0)

k.times do
  d = gets.to_i
  a = gets.chomp.split.map(&:to_i)
  a.each do |i|
    arr[i] += 1
  end
end

puts arr.select{ |a| a == 0 }.size - 1


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

int main() {
    long long a, b, v, w, t;
    cin>>a>>v;
    cin>>b>>w;
    cin>>t;
    long long relv = v - w;
    if(relv <= 0){
        cout << "NO" << endl;
        return 0;
    }
    long long reld = b - a;
    if(reld < 0){
        reld = reld * (-1);
    }
    double tim = (double)reld / (double)relv;
    //cout<< tim;
    if(tim <= (double)t){
        cout<<"YES"<<endl;
        return 0;
    }
    cout<<"NO"<<endl;
	// your code goes here
	return 0;
}


Measured memory_bytes: 3528
#include <bits/stdc++.h>
using namespace std;
#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 SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};

double dist(pair<int,int> a, pair<int,int> b){
  return pow((pow((a.first - b.first),2) + pow((a.second - b.second),2)),0.5);
 
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll m,n;
  cin >> m >> n;
  cout << abs(m-2) * abs(n-2) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int a,b;
	cin >> a >> b;
	cout << a * b - a - b + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
long long int a,b;
  cin >> a >> b;
  if (a>=0 && a<b) cout << b-a <<endl;
  else if (a>=0 && b>0) cout << 1+(a-b)+1 << endl;
  else if (b<=0 && a<b) cout << b-a <<endl;
  else if (a<0 && b<a) cout << 1+(a-b)+1 <<endl;
  else cout << 1+abs(abs(a)-abs(b)) <<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int a[2000000];

int main(){
	int n;
	for(int i = 0; i < 2000000; i++){
		a[i] = 1;
	}
	for(int i = 2; i < 2000000; i++){
		if(a[i]){
			for(int j = i * 2;j < 2000000; j = j + i){
					a[j] = 0;
			}
		}
	}

	while(scanf("%d",&n) != EOF){
		for(int i = n - 1; i > 1; i--){
			if(a[i]){
				printf("%d ",i);
				break;
			}
		}
		for(int i = n + 1; i < 2000000; i++){
			if(a[i]){
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 8832
#include<bits/stdc++.h>
using  namespace std;
int main(){
  double x1,x2,y1,y2;
  cin>>x1>>y1>>x2>>y2;
  double disx=pow(abs(x1-x2),2);
  double disy=pow(abs(y1-y2),2);
  double disxy=sqrt(disx+disy);
  cout<<fixed<<setprecision(10);
  cout<<disxy<<endl;
  return 0;
}



Measured memory_bytes: 3280
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf=sizeof(Def)==sizeof(long long)?9e18:1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dp1[5010][5010]={0};
int dp2[5010][5010]={0};
ll gcd(ll a,ll b){
	return (b==0?a:gcd(b,a%b));
}
int main(){
	int n,m;
	cin>>n>>m;
	int ma=0;
	int gc=-1;
	rep(i,n){
		int a;cin>>a;
		ma=max(ma,a);
		if(gc==-1)gc=a;
		else gc=gcd(gc,a);
	}
	if(m<=ma&&m%gc==0)cout<<"POSSIBLE"<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
}











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

int main()
{
    int n;
    cin >> n;
    int total = 0, res;
    int spot[n + 1];
    spot[0] = 0;
    for (int i = 1; i < n + 1; i++)
    {
        cin >> spot[i];
    }
    for (int i = 1; i < n + 1; i++)
    {
        total += abs(spot[i] - spot[i - 1]);
    }
    total += abs(spot[n] - spot[0]);

    for (int i = 1; i < n + 1; i++)
    {
        res = total;
        if (i != n)
        {
            res = res + abs(spot[i + 1] - spot[i - 1]) - abs(spot[i] - spot[i - 1]) - abs(spot[i + 1] - spot[i]);
        }
        else
        {
            res = res + abs(spot[n - 1] - spot[0]) - abs(spot[n] - spot[0]) - abs(spot[n] - spot[n - 1]);
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
import math

def main():
    N, P = map(int, input().split())
    A = tuple(map(int, input().split()))

    even = 0
    odd = 0
    for i in range(N):
        if A[i] % 2:
            odd += 1
        else:
            even += 1

    if P:
        i = 1
    else:
        i = 0
    bisket1 = 0
    while i <= odd:
        bisket1 += (math.factorial(odd) // math.factorial(odd - i)) // math.factorial(i)
        i += 2

    bisket2 = 0
    i = 0
    while i <= even:
        bisket2 += (math.factorial(even) // math.factorial(even - i)) // math.factorial(i)
        i += 1

    print(bisket1 * bisket2)

main()


Measured memory_bytes: 3064
gets
h=Hash[gets.split.map(&:to_i).group_by{|e|e}]
s,e=h.keys.minmax
 
puts (e+e%2)/2 == s && h[s].size==e%2+1 && (s+1..e).all?{|e|h[e]&&h[e].size>=2} ? "Possible" : "Impossible"

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

double v[60];
signed main(){
    int n;
    cin>>n;
    REP(i,n) cin>>v[i];
    sort(v,v+n);
    double tmp=(v[0]+v[1])/2;
   // cerr<<tmp;
    for (size_t i = 2; i < n; i++)
    {
            tmp=(v[i]+tmp)/2;
    }
    printf("%.10f\n",tmp);
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

void main(void)
{
  int a;
  scanf("%d",&a);
  while(a/10>0){
    a%=10;
  }
  switch(a){
    case 2:case 4:case 5:case 7:case 9:
    puts("hon");
    break;

    case 0:case 1:case 6:case 8:
    puts("pon");
    break;

    case 3:
    puts("bon");
    break;
  }
}


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

using namespace std;

int main() {
  string s, t;
  cin >> s;
  cin >> t;
  
  int count = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] != t[i]) count++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 3468
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		System.out.println(f(n+1));
	}
	static HashMap<Long, Long> mb = new HashMap<>();
	public static long f(long n) {
		Long memo = mb.get(n);
		if (memo != null) return memo;
		if (n <= 2) {
			return n;
		}
		long res = f(n/2) + f((n-1)/2) + f((n+1)/2);
		res %= MOD;
		mb.put(n, res);
		return res;
	}
}



Measured memory_bytes: 9812
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

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

template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}

//ifstream f(".in");
//ofstream g(".out");

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen(".in", "r", stdin);
#endif

  int n;
  cin >> n;
  vector<int> v(n + 2);
  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
  }
  int cnt_neg = 0;
  for (int i = 1; i <= n; ++i) {
    cnt_neg += v[i] < 0;
  }
  if (cnt_neg % 2 == 0) {
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
      sum += abs(v[i]);
    }
    cout << sum << '\n';
  } else {
    long long sum = 0;
    int minn = numeric_limits<int>::max();
    for (int i = 1; i <= n; ++i) {
      minn = min(minn, abs(v[i]));
      sum += abs(v[i]);
    }
    cout << sum - 2LL * minn << '\n';
  }


#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}


Measured memory_bytes: 640
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let s: String = read();
    let v = read_vec::<i64>();
    let (goal_x, goal_y) = (v[0], v[1]);

    let s = s.split('T').map(|x| x.len()).collect::<Vec<_>>();

    let cur_x = s[0];
    let cur_y = 0;

    let mut lateral_moves = Vec::new();
    for (i, m) in s.iter().enumerate() {
        if i % 2 == 0 && i > 1 {
            lateral_moves.push(m);
        }
    }
    let mut longitudinal_moves = Vec::new();
    for (i, m) in s.iter().enumerate() {
        if i % 2 == 1 {
            longitudinal_moves.push(m);
        }
    }
    let max_grid: usize = 18000;

    let mut dp = vec![vec![false; max_grid]; lateral_moves.len() + 1];
    dp[0][(max_grid / 2 + cur_x) as usize] = true;
    for i in 0..lateral_moves.len() {
        for j in 1..max_grid {
            if dp[i][j] {
                dp[i + 1][j + lateral_moves[i]] = true;
                dp[i + 1][j - lateral_moves[i]] = true;
            }
        }
    }
    let x_succeeded = dp[lateral_moves.len()][(max_grid as i64 / 2 + goal_x) as usize];
    // println!("{:?}", (x_succeeded, (goal_x + 8000) as usize, &dp[lateral_moves.len()][8000..8005]));

    let mut dp = vec![vec![false; max_grid]; longitudinal_moves.len() + 1];
    dp[0][(max_grid / 2 + cur_y) as usize] = true;
    for i in 0..longitudinal_moves.len() {
        for j in 1..max_grid {
            if dp[i][j] {
                dp[i + 1][j + longitudinal_moves[i]] = true;
                dp[i + 1][j - longitudinal_moves[i]] = true;
            }
        }
    }
    let y_succeeded = dp[longitudinal_moves.len()][(max_grid as i64 / 2 + goal_y) as usize];

    if x_succeeded && y_succeeded {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 198908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, x, y;
    cin >> k >> x >> y;
    auto eval = [&]() {
        int z = abs(x) + abs(y);
        if (z == 0) {
            return 0;
        } else if (z == k) {
            return 1;
        } else {
            int res = max(2, (z + k - 1) / k);
            if (k % 2 == 1 && res % 2 != z % 2) {
                res++;
            }
            return res;
        }
    };
    if ((abs(x) + abs(y)) % 2 == 1 && k % 2 == 0) {
        cout << -1 << '\n';
        return 0;
    }
    bool neg_x = (x < 0), neg_y = (y < 0);
    x = abs(x);
    y = abs(y);
    vector<pair<int, int>> p;
    if (x + y != 0) {
        p.emplace_back(x, y);
    }
    for (int i = eval(); i > 2; i--) {
        if (x >= k) {
            x -= k;
        } else {
            y -= k;
        }
        p.emplace_back(x, y);
    }
    assert(eval() <= 2);
    if (eval() == 2) {
        assert((x + y) % 2 == 0);
        vector<int> a = {-k, -k, -x + y + k, -x + y - k};
        vector<int> b = {x + y + k, x + y - k, k, k};
        for (int i = 0; i < 4; i++) {
            int nx = (b[i] - a[i]) / 2;
            int ny = nx + a[i];
            if (abs(nx) + abs(ny) == k && abs(nx - x) + abs(ny - y) == k) {
                p.emplace_back(nx, ny);
                break;
            }
            assert(i != 3);
        }
    }
    cout << p.size() << '\n';
    reverse(p.begin(), p.end());
    for (auto &z : p) {
        if (neg_x) {
            z.first *= -1;
        }
        if (neg_y) {
            z.second *= -1;
        }
        cout << z.first << " " << z.second << '\n';
    }
    return 0;
}

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

int main() {
    string s,t,buf;
    int temp;
    cin >> s >> t;
    int len = t.length();
    int dif = s.length() - t.length();
    int min = t.length();
    for(int i = 0; i <= dif; i++){
        temp = 0;
        buf = s.substr(i, len);
        for(int j = 0; j < len; j++){
            if(buf[j] != t[j]){
                temp++;
            }
        }
        if(temp < min){
            min = temp;
        }
    }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 3588
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        final int inputNum = scan.nextInt();
        ArrayList<Float> values = new ArrayList<Float>(inputNum);
        int value = 0;
        for(int i = 0; i < inputNum; i++){
            value = scan.nextInt();
            values.add((float)value);
        }
        for(int i = 0; i < inputNum; i++){
            // 昇順にソート
            Collections.sort(values);
            // 1番目と2番目を合成してリストに格納
            values.add((values.get(0) + values.get(1)) / (float)2);
            // 1番目と2番目を削除
            values.remove(0);
            values.remove(0);
            if(values.size() == 1){
                break;
            }
        }
        System.out.println(values.get(0));
        
        scan.close();
    }
  
}

Measured memory_bytes: 21972
def resolve():
    N = int(input())
    K = int(input())
    x = list(map(int, input().split()))
    
    sum = 0
    for i in range(N):
        if abs(K-x[i]) > x[i]:
            sum += x[i]*2
        else:
            sum += abs(K-x[i])*2
    print(sum)
resolve()


Measured memory_bytes: 38256
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>
#include <time.h>
#include <random>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
double Pi = 3.1415926535897932384626;
 
vector<ll> G[500005];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
 
 
ll mod = 1000000007;
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

 
//ll fact[800005],rfact[800005];
/*
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[800000] = rui(fact[800000],mod - 2);
    for(ll i=800000; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,ans,a,b,c,d,e,g,h,w,i,j,k,q;
ll x[500005],y[500005],z[500005];
char s[500005],t[500005];
 
int main(){
    cin >> n;
    for(i=0;i<n;i++){
        cin >> x[i];
    }
    sort(x,x+n);
    for(i=0;i<n-1;i++){
        if(x[i] != x[i+1])a++;
    }
    a += 1;
    if(a == 1){
        Yes(x[0] == 0);
    }else if(a == 2){
        Yes(x[0] == 0 && x[n/3] != 0 && x[n/3 - 1] == 0 && n % 3 == 0);
    }else if(a == 3){
        Yes(n % 3 == 0 && x[n/3] != x[n/3-1] && x[n/3 * 2] != x[n/3 * 2 - 1] && (x[0] ^ x[n/3]) == x[n/3 * 2]
            );
    }else{
        Yes(0);
    }

    return 0;
}












Measured memory_bytes: 14464
/*
Md.Shahnewaz Siddique Labib
Dept. of CSE
IUT,19
*/
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair

using namespace std;

int main(){
    fastio;
    ll n, moves;
    cin >> n;
    moves = n;
    for(long long i = 1; i*i < n + 1; i++) if(n%i == 0) moves = min(moves, i + n/i - 2);
    cout << moves;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, a, n) for (int i = a; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define EPS 1e-15
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;
}

const long long INF = 1LL << 60;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> ti3;

int N, K;
ll h[100110];
ll dp[100110];

int main()
{
    cin >> N >> K;
    rep(i, N)
    {
        cin >> h[i];
    }
    rep(i, 100010)
    {
        dp[i] = INF;
    }
    dp[0] = 0;

    rep(i, N)
    {
        for (int j = 1; j <= K; j++) {
            chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }
    cout << dp[N - 1] << "\n";
}


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

int main() {
    int N, K;
    std::string S;
    std::cin >> N >> K >> S;

    std::vector<int> segs({0});
    // [0][1][0][1][0][1][0][1][0]...
    if (S[0] == '0') segs.push_back(0);
    int L = 0;
    for (int i = 0; i < N; ++i) {
        ++L;
        if (i == N - 1 || S[i] != S[i + 1]) {
            segs.push_back(L);
            L = 0;
        }
    }
    for (int i = 1; i < segs.size(); ++i) segs[i] += segs[i - 1];

    int ans = 0;
    for (int l = 0; l < segs.size(); l += 2) {
        int r = std::min((int)segs.size() - 1, l + K * 2 + 1);
        ans = std::max(ans, segs[r] - segs[l]);
    }

    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 1020
while 1:
	n = raw_input()
	if n == "0000":break
	n = list(n)
	done = False
	for x in xrange(99):
		if "".join(n) == "6174":
			print x
			done = True
			break
		n.sort()
		m = "".join(n)
		n = list(str(int(m[::-1]) - int(m)))
		while(len(n) < 4):n = ['0'] + n
	if not done:
		print "NA"
	

Measured memory_bytes: 4224
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n, k;
	int m;
	int cnt1=0, cnt2=0;
	int max1=1,max2=1;
	bool f;
	while (cin >> n >> k, n)
	{
		int card[100001] = { 0 };
		for (int i = 0;i < k;i++)
		{
			cin >> m;
			card[m] = 1;
		}
		cnt1 = cnt2 = max1 = max2 = 0;
		f = false;
		//cout << "1A" << n << endl;
		for (int i = 1;i <= n;i++)
		{
			cnt1 = 0;
			while (card[i] == 0 && i<= n) i++;
			while (card[i] == 1 && i<=n)
			{
				cnt1++;
				i++;
			}
			if (f)
			{
				cnt2 += cnt1;
				if (max2 < cnt2) max2 = cnt2;
				f = false;
			}
			if (card[i + 1] == 1)
			{
				cnt2 = cnt1;
				f = true;
			}
			//cout << "AA" << i  << " " << max1 << " " << cnt1 << endl;
			//cout << "BB" << max2 << endl;
			if (max1 < cnt1) max1 = cnt1;
		}
		if (card[0] == 0)
		{
			cout << max1 << endl;
		}
		else
		{
			if (max1 < max2)
			{
				max1 = max2;
			}
			cout << max1 + 1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3396
#include<iostream>
#include<string>
using namespace std;
int main() {
	string s; cin >> s;
	int len = s.length();
	if (s[0] == s[len - 1]) {
		if (len % 2)cout << "Second" << endl;
		else cout << "First" << endl;
	}
	else {
		if (len % 2)cout << "First" << endl;
		else cout << "Second" << endl;
	}
	return 0;
}

Measured memory_bytes: 512
package main

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

type Product struct {
	Price    int64
	Quantity int
}

type ArrProduct []Product

func (a ArrProduct) Len() int           { return len(a) }
func (a ArrProduct) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ArrProduct) Less(i, j int) bool { return a[i].Price < a[j].Price }

func main() {
	var N, M, t int
	var total int64
	fmt.Scan(&N, &M)
	arr := make([]Product, N)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < N; i++ {
		sc.Scan()
		A, _ := strconv.ParseInt(sc.Text(), 10, 64)
		arr[i].Price = A
		sc.Scan()
		B, _ := strconv.Atoi(sc.Text())
		arr[i].Quantity = B
	}
	sort.Sort(ArrProduct(arr))
	for i := 0; i < M && t < M; i++ {
		q := arr[i].Quantity
		for j := 0; j < q && t < M; j++ {
			total += arr[i].Price
			t++
		}
	}
	fmt.Println(total)
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
	// your code goes here
	double h,w;
	cin>>h>>w;
	if(h==1 || w==1)
	cout<<1;
	else
	cout<<setprecision(20)<<ceil((h*w)/2);
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
#define F first
#define S second

const int mxn = 2e5+5;
int n, a[mxn], lis[mxn], ans[mxn];
bool v[mxn];
vector<int> adj[mxn];

void dfs(int node, int len){
    v[node] = true;

    int ind = -1, oldval = -1;
    if(len == 0 || a[node] > lis[len-1]){
        lis[len] = a[node];
        len++;
    }
    else{
        ind = lower_bound(lis, lis+len, a[node]) - lis;
        oldval = lis[ind];
        lis[ind] = a[node];
    }
    ans[node] = len;

    for(int next : adj[node]){
        if(!v[next]){
            dfs(next, len);
        }
    }

    if(ind != -1){
        lis[ind] = oldval;
    }
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n-1; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(0, 0);
    for(int i = 0; i < n; ++i) cout << ans[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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

#define REP(i,num) for(ll i=0;i<(num);++i)
#define FOR(i,c,num) for(ll (i)=(c);(i)<(num);++(i))
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){ T x; cin >> x; return (x); }
template<typename T=ll,typename C=vector<T>>
C vecin(int N){ C x(N);REP(i,N){ x[i]=in<T>(); }return x; }

void vout(){ cout << endl; }
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){ cout << ' ' << h;vout(forward<Tail>(t)...); }
void out(){ cout << endl; }
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){ cout << h;vout(forward<Tail>(t)...); }

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

vll M;

ll powermod(ll a,ll b,ll m){
	if(b==0){
		return 1LL;
	}
	if(b%2){
		return (a*powermod(a,b-1LL,m))%m;
	}
	return powermod((a*a)%m,b/2LL,m);
}

ll dfs(ll v){
	if(M[v]>=0) return M[v];

	ll B=0,V=v;
	while(V){
		if(V&1) B++;
		V/=2;
	}

	if(!B){
		M[v]=0;
		return 0;
	}
	if(!(v%B)){
		M[v] = 1;
		return 1;
	}

	ll C = dfs(v%B)+1;
	M[v] = C;
	return C;
}

ll safemod(ll a,ll m){
	return (a%m+m)%m;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	auto N=in();
	string X=in<string>();
	M.resize(N+1,-1);
	ll C=0;
	REP(i,N){
		if(X[i]=='1'){
			C++;
		}
	}
	ll modP=0,modD=0;
	vll powermodP(N),powermodD(N);
	if(C<N){
		REP(j,N){
			powermodP[j] = powermod(2,j,C+1);
			if(X[N-1-j]=='1'){
				modP += powermodP[j];
				modP %= (C+1);
			}
		}
	}
	if(C>1){
		REP(j,N){
			powermodD[j] = powermod(2,j,C-1);
			if(X[N-1-j]=='1'){
				modD += powermodD[j];
				modD %= (C-1);
			}
		}
	}

	ll K[2]={C-1,C+1};
	REP(i,N){
		ll B;
		auto T=X;
		ll mod=0;
		if(T[i]=='0'){
			T[i] = '1';
			B = 1;
			mod = modP;
			mod += powermodP[N-1-i];
			mod %= K[B];
		}
		else{
			T[i] = '0';
			B = 0;
			if(K[B]==0){
				out(0);
				continue;
			}
			mod = modD;
			mod -= powermodD[N-1-i];
			mod = safemod(mod,K[B]);
		}

		ll Z=1;
		while(mod){
			Z++;
			ll P=0,V=mod;
			while(V){
				if(V&1) P++;
				V/=2;
			}
			mod %= P;
		}
		out(Z);
	}


	return 0;
}


Measured memory_bytes: 8360
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in, n) for(int i=0; i<n; i++) cin>>in[i]
#define forout(out, n) for(int i=0; i<n; i++) cout<<out[i]<<endl

int main(){
    int N, K; cin>>N>>K;
    ll A[N];
    forin(A, N);
    for(int i=K; i<N; i++){
        if(A[i]>A[i-K]){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
}


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

int main(){
	ll n,m;
	cin >> n >> m;
	ll p[1000000],y[1000000];
	vector<pair<ll,pair<ll,ll> > > vec(m);
	ll num_u[1000000] = {0},num_d[1000000] = {0},rank[1000000] = {0};
	
	rep(i,0,m){
		cin >> p[i] >> y[i];
		vec[i] = make_pair(p[i],make_pair(y[i],i));
	}
	
	sort(vec.begin(),vec.end());
	
	rep(i,0,m){
		num_u[vec[i].second.second] = p[vec[i].second.second];
		num_d[vec[i].second.second] = ++rank[vec[i].first-1];
	}	
	
	
	rep(i,0,m){
		ostringstream sout;
		sout << setfill('0') << setw(6) << num_u[i];
		string s = sout.str();
		cout << s;
		
		ostringstream sout2;
		sout2 << setfill('0') << setw(6) << num_d[i];
		string s2 = sout2.str();
		cout << s2 << endl;
	}
	
  	return 0;
}





Measured memory_bytes: 34688
N = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans = factorization(N)
index = [ans[i][1] for i in range(len(ans))]
k = 0
if N == 1:
  print('0')
else:
  
  for i in range(len(ans)):
    a = index[i]
    j = 1
    while a - j >=0:
      k += 1
      a -= j
      j += 1
  print(k)    


Measured memory_bytes: 9496