akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define PRINT2(n,m) cout << n << " " << m << "\n";
void Main();
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main(){
    int a, b;
    cin >> a >> b;
    PRINT2(a*b,(2*a)+(2*b))
}


Measured memory_bytes: 3040
fun main(args: Array<String>) {
    edpd()
}

fun edpd() {
    val (n, weightLimit) = readLine()!!.split(" ").map { it.toInt() }
    val items = (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
        .map { Item(it[0], it[1]) }

    val dp = Array(n + 1) { LongArray(weightLimit + 1) }

    for (i in items.indices) {
        val (weight, price) = items[i]
        for (wl in 0..weightLimit) {
            dp[i + 1][wl] = Math.max(dp[i + 1][wl], dp[i][wl])
            if (wl + weight <= weightLimit) {
                dp[i + 1][wl + weight] = Math.max(dp[i + 1][wl + weight], dp[i][wl] + price)
            }
        }
    }

    val answer = dp[n][weightLimit]

    println(answer)
}

data class Item(val weight: Int, val price: Int)


Measured memory_bytes: 122952
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define dF2(i,a,b) for(int i=(a);i>(b);--i)
#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)
using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;

int n,m,Ans;
char str[2005];
int a[2001][2001], b[2001][2001];
int h[2001];
int l[2001],r[2001];
int s[2001],t;

int main(){
	scanf("%d%d",&n,&m); Ans=n;
	F(i,1,n){
		scanf("%s",str+1);
		F(j,1,m) a[i][j]=str[j]=='#';
		F(j,2,m) b[i][j-1]=a[i][j-1]^a[i][j];
	}
	F(j,1,m-1) h[j]=1;
	F(i,2,n){
		F(j,1,m-1) if(b[i][j]==b[i-1][j]) ++h[j]; else h[j]=1;
		s[t=1]=0;
		F(j,1,m-1){
			while(t&&h[s[t]]>=h[j]) --t;
			l[j]=s[t];
			s[++t]=j;
		}
		s[t=1]=m;
		dF(j,m-1,1){
			while(t&&h[s[t]]>=h[j]) --t;
			r[j]=s[t];
			s[++t]=j;
		}
		F(j,1,m-1) Ans=max(Ans,h[j]*(r[j]-l[j]));
	} printf("%d",Ans);
	return 0;
}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
    int n, w[200];
    cin >> n;
    rep(i, n){
        cin >> w[i];
    }
    int max_dif, l[n+10], d[n+10];
    l[0] = w[0];
    rep(i, n-1){
        l[i+1] = w[i+1] + l[i];
    }
    d[n-2] = w[n-1];
    for(int i = n-3; i >= 0; i--){
        d[i] = w[i+1] + d[i+1];
    }
    bool tmp = false;
    rep(i, n-1){
        if(d[i]-l[i] < 0) {
            cout << min(abs(d[i]-l[i]),abs(d[i-1]-l[i-1])) << endl;
            tmp = true;
            break;
        }
    }
    if(tmp == false) cout << "0" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define F first
#define S second
typedef vector<pli> vpli;
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end() 
#define tests int t; cin>>t; while(t--)
#define take(a,b,c) for(b=0;b<c;b++) cin>>a[b];
#define INF 1e18
// https://codeforces.com/problemset/page/3?tags=1500-1800
int main()
{	
  //auto start = std::chrono::high_resolution_clock::now();
  long double l;
  cin>>l;
  long double x  = l/3;
  cout<<fixed<<setprecision(12)<<(x*x*x);
  //auto stop = std::chrono::high_resolution_clock::now(); 
  //auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
  //cout << duration.count() << endl; 

}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int M = sc.nextInt();
      int[] H = new int[N];
      for(int i=0;i<N;i++){
        H[i] = sc.nextInt();
      }
      boolean[] check = new boolean[N];
      for(int i=0;i<N;i++){
        check[i] = true;
      }
      for(int i=0;i<M;i++){
        int A = sc.nextInt()-1;
        int B = sc.nextInt()-1;
        if(H[A]<=H[B]){
          check[A]=false;
        }if(H[A]>=H[B]){
          check[B]=false;
        }
      }
      int ans = 0;
      for(int i=0;i<N;i++){
        if(check[i]){
          ans++;
        }
      } 
      System.out.println(ans);
    }
}

Measured memory_bytes: 59708
#![allow(clippy::needless_range_loop)]
#![allow(unused_macros)]
#![allow(dead_code)]

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut 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 main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let ans = a.iter().zip(1..=n).filter(|(a, b)| *a % 2 == 1 && *b % 2 == 1).count();
    println!("{}", ans);
}


Measured memory_bytes: 2108
n,m = map(int,input().split())

adj = [[]for _ in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1

    adj[a].append(b)
    adj[b].append(a)

from collections import deque
q = deque()

dist = [-1]*n
ans = [0]*n

q.append(0)
while q:
    now = q.popleft()
    for to in adj[now]:
        if dist[to] != -1:continue
        dist[to] = dist[now] + 1
        q.append(to)
        ans[to] = now

print('Yes')
for i in range(1,n):
    print(ans[i] + 1)
'''
catupperさんのコードを写経しました。
'''



Measured memory_bytes: 95856
#include <bits/stdc++.h>
#define ll long long
#define pds pair<double, string>
using namespace std;

struct info {
    string name;
    double rate;
};

bool operator<(const info &a, const info &b) {
    if (a.rate != b.rate) {
        return a.rate <= b.rate;
    } else if (a.rate == b.rate) {
        return a.name > b.name;
    }
}

int main() {
    int n;
    while (cin >> n, n) {
        vector<info> v;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            double p, a, b, c, d, e, f, ss, m;
            cin >> p >> a >> b >> c >> d >> e >> f >> ss >> m;
            double fi = (a + b + c + d + e);
            double se = (d + e);
            double sum = fi + se * (m - 1);
            double val = m * f * ss - p;
            v.push_back((info){s, val / sum});
        }
        sort(v.begin(), v.end());
        for (int i = n - 1; i >= 0; i--) {
            cout << v[i].name << endl;
        }
        cout << "#" << endl;
    }
    return 0;
}


Measured memory_bytes: 3204
import java.util.*;

public class Main {
  public static void main(String[] args) {
    int N;
    try(Scanner sc = new Scanner(System.in)) {
      N = sc.nextInt();
    }
    int maxKeta = (int)Math.floor(Math.log10((double)N) + 1);
    int answer = 0;
    if ( maxKeta >= 2 ) {
	    int n = (int)Math.floor((maxKeta - 2)/2);
    	int M = 2 * n + 1;
    	answer += ((int)(Math.pow(-10,(M+1)))-1)/11;
    }
    if ( maxKeta % 2 == 1 ) {
      answer += N - (int)(Math.pow(10,maxKeta-1)) + 1;
    }
    System.out.println(answer);
  }
}

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

int main()
{
  string A, B;
  cin >> A >> B;
  if(A.length() > B.length()) {
    cout << "GREATER" << endl;
    return 0;
  } else if(A.length() < B.length()) {
    cout << "LESS" << endl;
    return 0;
  } else {
    for(int i=0; i<A.length(); ++i) {
      if(A[i] > B[i]) {
        cout << "GREATER" <<endl;
        return 0;
      } else if(A[i] < B[i]) {
        cout << "LESS" << endl;
        return 0;
      }
    }
  }
  cout << "EQUAL" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define PUT(x) cout << x << endl
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };

int main(void)
{

	string s, t;
	cin >> s >> t;

	if ((int)sqrt(stoi(s + t)) * (int)sqrt(stoi(s + t)) == stoi(s + t)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer return cout << "NO", 0;
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 1e5 + 200;
const long long MNN = 3e3 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e13;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong n, k, a[102][102], dp[20000000];

void add(llong& a, llong b){
    a += b;
    while(a < 0) a += MOD;
    a %= MOD;
}

int main () {
    ios;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    dp[0] = 1;
    for(int i = 0; i < (1 << n); i++){
        int lol = __builtin_popcount(i);
        for(int j = 0; j < n; j++){
            if(a[lol][j] == 1 && !((1 << j) & i)){
                llong kek = i ^ (1 << j);
                add(dp[kek], dp[i]);
            }
        }
    }
    cout << dp[(1 << n) - 1];
}


Measured memory_bytes: 18688
#include <stdio.h>
#include <iostream>
#include <tuple>
#include <queue>
#include <algorithm>
#include <string>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <time.h>
#include <assert.h>
#include <stack>
#include <deque>
#include <bits/stdc++.h>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <sstream>  // istringstream buffer(myString);
// #include <boost/functional/hash.hpp>

using namespace std;

#define endl "\n";
#define bit(x, i) (x&(1<<i))  //select the bit of position i of x
#define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x; example: x=12;  1100 => 100 => 4
#define LL long long
#define ULL unsigned long long
LL inf = 1e9+7;
LL mod = 1e9+7;
#define PII pair<int, int>
#define V vector
#define VI vector<int>
#define VS vector<string>
#define ALL(x) x.begin(), x.end() //handy for function like "sort()"
#define pi 3.14159265358979323846
// set a to the maximum of a and b
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
// conversion
string removeZeros(string str) { return str.erase(0, min(str.find_first_not_of('0'), str.size()-1)); } // remove leading zeros
#define char2int(c) (c-'0')
#define int2char(i) (static_cast<char>(i))
#define bin2int(bin) (bitset< 1001 >(bin).to_ulong())
#define int2bin(i) removeZeros(bitset< 1001 >( i ).to_string())
// str.erase(0, min(str.find_first_not_of('0'), str.size()-1)); // remove leading zeros

void reverseStr(string& str) { 
    int n = str.length(); 
    for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); 
} 

// works for unordered_set, unordered_map..
#define HMAP unordered_map
#define SET unordered_set
#define HAS(umap, key) (umap.find(key) != umap.end())
#define COUNTER(m, j) if (HAS(m, j)) { m[j]++; } else { m[j] = 1; }
// loop
#define FOREACH(vec, i) for (auto i = vec.begin(); i!= vec.end(); i++)
// read line
#define READ_INTS(vec, n) vector<LL> vec(n); for (LL i=0; i<n; i++) { cin >> vec[i]; }; cin.ignore();
#define READ_DOUBLES(vec, n) vector<double> vec (n); FOREACH(vec, i) { cin >> *i; }; cin.ignore();
#define READ_STRING(vec) string vec; getline(cin, vec);
#define READ_INT(i) LL i; cin >> i; cin.ignore();
// #define SPLIT_STRINGS(vec, str) istringstream iss(str); vector<string> vec((istream_iterator<string>(iss)), istream_iterator<string>());
// debug
#define dd(var) cerr << #var << "=" << (var) << " | "
#define ddv(vec) FOREACH(vec, i) { cout << *i << " "; } cout << endl;
#define ddvv(vec) for(auto& i:vec) { for(auto& j:i) { cout <<  j << " "; }; cout << endl };

void solve() {
    LL a, b, c, d, res, cnt;
    cin >> a >> b;
    c = max(a, b);
    d = min(a, b);

    res = 0;
    cnt = 2;
    while(cnt) {
        if (c >= d) {
            res += c;
            c -= 1;
        } else {
            res += d;
            d -= 1;
        }
        cnt--;
    }
    cout << res << endl;



}


int main()
{  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
//   READ_INT(t);
//   for (LL i = 0; i < t; i++) {
    solve();
//   }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=2010;
ll n,f[N];

int main()
{
	cin>>n;
	for(int i=3;i<=n;i++)
	{
		f[i]=1;
		for(int j=3;j<=i;j++)
			f[i]=(f[i-j]+f[i])%mod; 
	}
//	ll ans=0;
//	for(int i=1;i<=n/3;i++) ans=(ans+f[n][i])%mod;
	cout<<f[n];
	
	return 0;
} 

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string s;
    cin >> s;

    int min = 99999999;
    for (int i = 0; i < s.size()-2; i++)
    {
        string numStr = "";
        numStr.append(s, i, 3);

        int num = atoi(numStr.c_str());
        int diff = abs(753 - abs(num));
        if (diff < min)
        {
            min = diff;
        }
    }
    

    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

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

int main() {
	int a, b, c, d, p;
	int x, y;
	cin >> a >> b >> c >> d >> p;

	x = a * p;
	
	y = b;
	if (p > c) y += (p - c) * d;

	cout << min(x, y) << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int main() {
	int n, l;
	std::cin >> n >> l;
	
	int first = l, last = l + n - 1;
	
	int sum;
	if(n % 2){
	    sum = (first + last) * (n / 2) + (first + last) / 2;
	}else{
	    sum = (first + last) * (n / 2);
	}
	
	if(first < 0 and last < 0){
	    std::cout << sum - last << std::endl;
	    
	}else if(first < 0 and last >= 0){
	    std::cout << sum << std::endl;
	    
	}else{
	    std::cout << sum - first << std::endl;
	}
    
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    pair<int, int> p[m];
    for (int i = 0; i < m; i++) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p, p+m);
    int ans = 0, a = p[0].first, b = p[0].second;
    for (int i = 1; i < m; i++) {
        if (b <= p[i].first) {
            ans++;
            // a = p[i].first;
            b = p[i].second;
        } else
            b = min(b, p[i].second);
    }
    cout << ans + 1 << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

void dfs(Vvec<int>& graph, vector<int>& par, 
    vector<int>& d1, vector<int>& d2,
    int tmp, int from)
{
    // cout << tmp << endl;
    par[tmp] = from;
    d1[tmp] = (from == -1) ? 0 : d1[from]+1;
    if(from != -1 && graph[tmp].size() == 1){
        d2[tmp] = 0; return;
    }

    for(int& to: graph[tmp]){
        if(to != from){
            dfs(graph, par, d1, d2, to, tmp);
            d2[tmp] = max(d2[tmp], d2[to]+1);
        }
    }
}

int main()
{
    int N, u, v;
    cin >> N >> u >> v;
    u--; v--;
    Vvec<int> graph(N);
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> par(N), d1(N, 0), d2(N, 0);
    dfs(graph, par, d1, d2, v, -1);

    int ans = 0;
    int itr = 0;
    while(u != v){
        if(d1[u]-itr<=0){
            ans = max(ans, itr); break;
        }
        ans = max(ans, itr + d2[u] + (d1[u]-itr-1));
        u = par[u];
        if(d1[u]==itr){
            ans = max(ans, itr); break;
        }
        itr++;
    }

    cout << ans << endl;
    // for(int i=0; i<N; i++) cout << d2[i] << " "; cout << endl;
}

Measured memory_bytes: 14592
import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int [] A = new int [N];
        int a = 1;
        int b = 1;
        for(int i=0; i<N; i++){
            A[i] = sc.nextInt();
        }
        
        for(int i=0; i<N; i++){
            a*=3;
            if(A[i]%2 ==0) b*=2;
        }
        
        System.out.println(a-b);
        
    }
}


Measured memory_bytes: 35608
import sys
import functools
from math import gcd


def lcm2(x, y):
    return x * y // gcd(x, y)


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N, M = map(int, next(in_).split())
    A = tuple(map(lambda x: int(x) // 2, next(in_).split()))

    a0 = A[0]
    x = 0
    while True:
        a0, b = divmod(a0, 2)
        if b:
            break
        x += 1
    x = 2 ** x
    for a in A[1:]:
        d, m = divmod(a, x)
        if m != 0 or not d % 2:
            return 0 

    l = lcm(A)
    l2 = l + l

    answer = len(range(l, M + 1, l2))

    return answer


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19260
import java.util.Scanner;
  
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String strW = sc.next();
    int x = 0;
  
    for(int i = 0; ; i++){
      String str = sc.next();
      String str2 = "";
      for(int n = 0; n < str.length(); n++){
        char c = str.charAt(n);
        if('A' <= c && c <= 'Z'){
          c += 'a' - 'A';
        }
        str2 += c;
      }
      if(str2.equals(strW)){
        x += 1;
      }
      if(str.equals("END_OF_TEXT")){
        break;
      }
    }
  
    System.out.println(x);
  }
}


Measured memory_bytes: 26320
#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 INF (1<<29)

vector<bool> used;
long long sum[1000001];

int main() {
	used.resize(1000001, false);
	used[0] = used[1] = true;
	for (int i = 2; i * i <= 1000001; i++) {
		if (!used[i]) {
			sum[i]++;;
			for (int j = i; j <= 1000001; j += i) used[j] = true;
		}
	}
	REP(i, 1000001) if (!used[i]) sum[i]++;
	
	FOR(i, 1, 1000001) sum[i] += sum[i - 1];
	
	int n;
	while (cin >> n, n) {
		long long ans = 0;
		REP(i, n) {
			int p, m;
			scanf("%d %d", &p, &m);
			
			int a = p - m < 0 ? 0 : p - m - 1;
			int b = p + m > 1000001 ? 1000000 : p + m;
			
			int cnt = sum[b] - sum[a];
			if (cnt == 0) ans--;
			else ans += cnt - 1;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 9176
from collections import Counter
 
S = list(input())
T = list(input())
 
SS = Counter(S)
TT = Counter(T)
 
SS = list(SS.values())
SS.sort()
 
TT = list(TT.values())
TT.sort()
 
if SS == TT:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 6960
//
// Created by in on 20/7/25.
//

#include<bits/stdc++.h>

using namespace std;

void printArray (int* arr, int size);

void insertionSort (int* arr, int size);

int main ()
{
	int n;
	int a[100];

	cin >> n;
	for(int i = 0; i < n; ++i)
	{
		scanf("%d", &a[i]);
	}
	printArray(a, n);
	insertionSort(a, n);

	return 0;
}

void printArray (int* arr, int size)
{
	int i = 0;
	for(; i < size - 1; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("%d\n", arr[i]);
}

void insertionSort (int* arr, int size)
{
	int tmp;
	for(int i = 1; i < size; ++i)
	{
		tmp = arr[i];
		int j = i - 1;
		while(j >= 0 && arr[j] > tmp)
		{
			arr[j + 1] = arr[j];
			--j;
		}

		arr[j + 1] = tmp;
		printArray(arr, size);

	}
}


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

const int maxN = 102, inf = 1e9;

int n, m;
int f[maxN + 1][maxN + 1];
bool g[maxN + 1][maxN + 1][maxN + 1][maxN + 1][2];
char s[maxN + 1][maxN + 1];

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);

	for(int a = 1; a <= n; a++)
		for(int b = 1; b <= m; b++)
		{
			if(s[a][b] == '.') g[a][b][a][b][0] = true;
			else g[a][b][a][b][1] = true;
			for(int c = a; c <= n; c++)
				for(int d = b; d <= m; d++)
				{
					if(c == a && d == b) continue;
					if(s[c][d] == '.') g[a][b][c][d][0] = g[a][b][c - 1][d][0] || g[a][b][c][d - 1][0];
					else g[a][b][c][d][1] = g[a][b][c - 1][d][1] || g[a][b][c][d - 1][1];
				}
		}

	for(int i = 0; i <= n; i++) f[i][0] = inf;
	for(int i = 0; i <= m; i++) f[0][i] = inf;

	if(s[1][1] == '.') f[1][1] = 0;
	else f[1][1] = 1;
	for(int a = 1; a <= n; a++)
		for(int b = 1; b <= m; b++)
		{
			if(a == 1 && b == 1) continue;
			f[a][b] = inf;
			for(int c = 1; c <= a; c++)
				for(int d = 1; d <= b; d++)
				{
				//	printf("%d %d %d %d %d %d\n", a, b, c, d, g[c][d][a][b][0], g[c][d][a][b][1]);
					int t = min(f[c - 1][d], f[c][d - 1]);
					if(c == 1 && d == 1) t = 0;
					if(g[c][d][a][b][0]) f[a][b] = min(f[a][b], t);
					if(g[c][d][a][b][1]) f[a][b] = min(f[a][b], t + 1);
				}
		}

	printf("%d", f[n][m]);
	return 0;
}


Measured memory_bytes: 215296
/* ex3_1
  terakura */

#include <stdio.h>

int main(void){

    int n, bace, digits = 0;

    scanf("%d %d", &n, &bace);

  //nをbaceで割った商が0になるまで繰り返す
    while(n>0){
      n = n/bace;    //nにnをbで割った商を代入
      digits++;    //digitsに１をたす
    }

    printf("%d\n", digits);    //桁数を出力

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  string N;
  cin>>N;
  if(N.at(0) =='7')
    cout<<"Yes"<<endl;
  else if(N.at(1) == '7')
    cout<<"Yes"<<endl;
  else if(N.at(2) == '7')
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}
  

Measured memory_bytes: 3596
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>


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

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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


int main() {
    ll n, sum = 0, mn = INF;
    bool ok = false;
    
    cin >> n;
    
    ll a, b;
    REP(i, n){
        cin >> a >> b;
        
        if(a > b){
            ok = true;
            mn = min(mn, b);
        }
        sum += a;
    }
    
    if(ok){
        cout << sum - mn << endl;
    }
    else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n>>m;
    m = 2*m+1;
    cout<<(n+m-1)/m;

    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

namespace
{
	ll GCD(ll a, ll b)
	{
		return a == 0 ? b : GCD(b % a, a);
	}
}

void ABC142D()
{
	ll A, B;
	cin >> A >> B;
	ll C = GCD(A, B);
	ll sqrtC = static_cast<ll>(sqrt(static_cast<long double>(C)));

	map<ll,int> x;
	x[1] = 1;
	int i = 2;
	while (i <= sqrt(C))
	{
		while (C % i == 0)
		{
			++x[i];
			C /= i;
		}
		++i;
	}
	if (C > 1)
		++x[C];

	int N = x.size();
	cout << N << endl;
}
int main()
{
	ABC142D();
	return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc057/tasks/abc057_c
n = int(input())

factors = []

i = 1
while i <= n ** 0.5:
    if n % i == 0:
        factors.append(i)
    i += 1

def func(a, b):
    A = len(str(a))
    B = len(str(b))
    return max(A, B)

ans = float('inf')
for f in factors:
    a, b = f, n // f
    t = func(a, b)
    ans = min(ans, t)
print(ans)

Measured memory_bytes: 39664
N, P = map(int, input().split())

rec = []
K = P
for i in range(2, int(P ** 0.5) + 1):
    if K % i == 0:
        tmp = 0
        while K % i == 0:
            tmp += 1
            K //= i

        rec.append((i, tmp))

if K != 1:
    rec.append((K, 1))

num = 1
for k, i in rec:
    q = i
    while q >= N:
        num *= k
        q -= N

print(num)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
const int INF = 1000000007;
int N;
int V[100001];
priority_queue<double, vector<double>, greater<double> >  que;

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

  cin >> N;
  double a;
  rep(i, N){
    cin >> a;
    que.push(a);
  };
  while(que.size()>1){
    double f = que.top();
    que.pop();
    double s = que.top();
    que.pop();
    double nxt = (f+s)/2.0;
    que.push(nxt);
  }
  cout << que.top() << endl;
  return 0;
}

Measured memory_bytes: 256
INTERVAL = 1
WHITE = 0
GRAY = 1
BLACK = 2


def depth_first_search(u):
    global time

    time += INTERVAL
    d[u] += time
    color[u] = GRAY

    for v in range(n):
        if matrix[u][v] and color[v] == WHITE:
            depth_first_search(v)

    time += INTERVAL
    f[u] += time
    color[u] = BLACK

# INPUT
n = int(input())


time = 0
color = [WHITE] * n
d = [0] * n
f = [0] * n

matrix = [[0] * n for _ in range(n)]

for i in range(n):

    u, k, *V = map(int, input().split())

    for v in V:
        v -= 1
        matrix[i][v] = 1


# PROCESS
u_search = 0
while True:

    depth_first_search(u_search)

    if WHITE not in color:
        break
    else:
        u_search = color.index(WHITE)
        

# OUTPUT
for i in range(n):
    print(i + 1, d[i], f[i])






Measured memory_bytes: 5788
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define For(i,n) for(int i=0;i<n;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define int long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MAXN 1000000


int A[MAXN], dp[MAXN][2], N, K;

int solve(int k, int m) {

  if (dp[k][m] != -1) return dp[k][m];
  if (k == 0) return m ^ 1;

  int ans = m ^ 1;
  for (int i = 1; i <= N; i++) {
    if (A[i] > k) continue;
    if (solve(k - A[i], m ^ 1) == m) {
      ans = m;
      break;
    }
  }

  return dp[k][m] = ans;

}

int32_t main() {

  memset(dp, -1, sizeof(dp));
  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }

  if (solve(K, 1)) printf("First\n");
  else printf("Second\n");

  return 0;

}

Measured memory_bytes: 21248
//Create Time: 2018-04-28 13:44:10
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <functional>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <ctime>
#include <utility>
#include <complex>
#include <cassert>
#include <climits>
#include <iterator>
#include <tuple>
using namespace std;
#define snuke(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,n,a) for (int i=(n)-1;i>=(a);i--)
// #define OUT(x) std::cout<<(#x)<<":"<<(x)<<std::endl
// #define TST(x) std::cout<<(#x)<<":"<<(x)<<" "
#define OUT(args...) {string _s=#args;replace(_s.begin(),_s.end(),',',' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);OUT_TST("\n",_it,args);}
#define TST(args...) {string _s=#args;replace(_s.begin(),_s.end(),',',' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);OUT_TST("",_it,args);}
#define SZ(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define unq(x) sort(all(x)),(x).erase(unique(all(x)),(x).end())
#define mem(f,x) memset((f), (x), sizeof(f))
#define clr(f) mem(f,0)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define eb emplace_back
#define DEBUG
void OUT_TST(string s,istream_iterator<string> it) {cerr<<s;}
template<typename T, typename... Args> void OUT_TST(string s,istream_iterator<string> it,T a,Args... args){cerr<<*it<<"="<<a<<" ";OUT_TST(s,++it,args...);}
template<class T> void rd(T&ret){ret=0;bool ok=0,u=0;for(;;){int c=getchar();if(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',ok=1;else if(c=='-')u=1;else if(ok){if(u)ret*=-1;return;}}}
long long powmod(long long p,long long n,long long mod){long long ret=1;for(;n;n>>=1){if(n&1)ret=ret*p%mod;p=p*p%mod;}return ret;}
template <class T> bool chmin(T& a, const T &b) {return b < a? a = b, 1: 0;}
template <class T> bool chmax(T& a, const T &b) {return b > a? a = b, 1: 0;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef tuple<int,int,int> tp;
/****head****/
int main(){
    int n,K;cin>>n>>K;
    ll ans=0;
    rep(t,K,n){
        int i=t+1,j,k=2;
        for(;i<=n;i=j+1){
            k=(n-t)/i;
            if(k==0)j=n;
            else j=(n-t)/k;
            if(t) ans+=(ll)(j-i+1)*(k+1);
            else ans+=(ll)(j-i+1)*k;
            // OUT(t,i,j,k,ans);
        }
        // if(i<=n)ans+=n-i+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
  string str1,str2;
  cin >> str1 >> str2;
  
  for(int i=0;i<str2.length()-1;i++){
    if(str1[i] != str2[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3624
using System;
using System.IO;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        private int N;
        private int[] A, B;
        static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            var sc = new Scanner();
            N = sc.NextInt();
            A = new int[N];
            B = new int[N];
            var array = (new int[N]).Select((i, index) => index).ToArray();
            for (int i = 0; i < N; i++)
            {
                A[i] = sc.NextInt();
                B[i] = sc.NextInt();
            }
            Array.Sort(array, (a, b) => B[a].CompareTo(B[b]));

            long sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += A[array[i]];
                if (B[array[i]] < sum)
                {
                    Console.WriteLine("No");
                    return;
                }
            }
            Console.WriteLine("Yes");
        }
    }
}



class Scanner
{
    public Scanner()
    {
        _stream = new StreamReader(Console.OpenStandardInput());
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private readonly StreamReader _stream;
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = _stream.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = _stream.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}


Measured memory_bytes: 20144
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
const ll mod=1e+9;
typedef pair<ll,ll> P;
#define fi first
#define se second

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,b;
cin>>n>>b;
int k=n,t=b;
vector<int> a;
a.push_back(b);
while(--k){
    t--;
    a.push_back(t);
}
k=n,t=b;
while(--k){
    t++;
    a.push_back(t);
}
sort(a.begin(),a.end());
for(int i=0;i<a.size();i++){
    cout<<a.at(i)<<" ";
}
cout<<endl;
}


Measured memory_bytes: 256
H, W = map(int,input().split())
A = [input() for i in range(H)]
q1 = []
q2 = []
visit = [[False]*W for i in range(H)]
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q1.append([i,j])
            visit[i][j] = True

while q1:
    while q1:
        index = q1.pop()
        for i in [-1,1]:
            for j in [-1,1]:
                if index[0]+i >= 0 and index[0]+i < H:
                    if not visit[index[0]+i][index[1]]:
                        visit[index[0]+i][index[1]] = True
                        q2.append([index[0]+i,index[1]])
                if index[1]+j >= 0 and index[1]+j < W:
                    if not visit[index[0]][index[1]+j]:
                        visit[index[0]][index[1]+j] = True
                        q2.append([index[0],index[1]+j])
    q1 = q2[:]
    q2 = []
    cnt += 1
    
print(cnt-1)




Measured memory_bytes: 155660
#include <iostream>
#include <math.h>
#define MOD 1000000007
using namespace std;
using ull = unsigned long long;

int main(){
    int N, ans = 1;
    cin >> N;

    ull base[N+1];
    ull primes[N+1];
    for(int i = 1; i <= N; ++i){
        base[i] = i;
    }

    for(int i = 2; i <= N; ++i){
        primes[i] = 1;
    }

    for(int i = 1; i <= N; ++i){
        int j = 2;
        while(base[i] != 1){
            if(base[i] % j == 0){
                base[i] /= j;
                primes[j]++;
            }else{
                j++;
            }
        }
    }
    for(int i = 2; i <= N; ++i){
        ans = (ans * primes[i]) % MOD;
    }

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


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define repd(i,a,b) for(int i = (a); i >= (b); i--)
#define repit(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define all(u) (u).begin(),(u).end()
#define rall(u) (u).rbegin(),(u).rend()
#define UNIQUE(u) (u).erase(unique(all(u)),(u).end())
#define pb push_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define PI acos(-1.0)

using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define dump(x) cerr<<#x<<" = "<<(x)<<endl;

int pw10[10] = {1};

void gen()
{
    repi(i,1,10)
        pw10[i] = pw10[i - 1] * 10;
}

int N, M;
vector<bool> nonzero;
vector<int> coef;

int ans, used;

void init()
{
    nonzero.clear();
    coef.clear();
    ans = used = 0;
}

void input()
{
    map<char,bool> nz;
    map<char,int> c;
    rep(i,N) {
        string s; cin >> s;
        if (s.length() >= 2)
            nz[s[0]] = true;
        rep(j,(int)s.length())
            if (i < N - 1)
                c[s[j]] += pw10[(int) s.length() - j - 1];
            else
                c[s[j]] -= pw10[(int) s.length() - j - 1];
    }
    repit(it,c) {
        nonzero.pb(nz[it->first]);
        coef.pb(it->second);
    }
    M = coef.size();
}

void dfs(int depth, int value)
{
    if (depth == M) {
        ans += value == 0;
        return;
    }
    if (!nonzero[depth] && ~used & 1) {
        used ^= 1;
        dfs(depth + 1, value);
        used ^= 1;
    }
    repi(i,1,10) {
        if (~used >> i & 1) {
            used ^= 1 << i;
            dfs(depth + 1, value + coef[depth] * i);
            used ^= 1 << i;
        }
    }
}

int main()
{
    gen();

    while (cin >> N && N) {
        init();
        input();
        dfs(0, 0);

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

Measured memory_bytes: 1232
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

class weightRtree:
    def __init__(self, num):
        self.num = num
        self.weight = [0] * (num+1) 
      
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v) & v    

    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u) & u
        return temp

N = int(input())
left = [0] * N
right = [0] * N
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count

Object = weightRtree(DFS(1, 0))

Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(right[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))




Measured memory_bytes: 143728
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
int N;
ll A,B;
int p[5000];
ll dp[5000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>A>>B;
    rep(i,0,N){
        cin>>p[i];
        p[i]--;
    }
    rep(i,0,N){
        bool t=false;
        int cnt=0;
        int u;
        rep(j,0,N){
            if(p[j]>i&&j>0){
                dp[j]=dp[j-1];
            }
            if(t&&p[j]<i){
                cnt++;
                dp[j]=min(A+dp[j], B*cnt+dp[u]);
            }
            if(p[j]==i){
                u=j;
                t=true;
            }
        }
    }
    cout <<dp[N-1]<<"\n";
}

Measured memory_bytes: 384
# Refer to:
# https://qiita.com/mochizukikotaro/items/c335e6dcc5020ead0b92
class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end
  
  def sum
    @data.inject(:+)
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def size
    @data.size
  end
  
  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx] > @data[target_idx])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    # child がある場合
    while (has_child?(target_idx))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      if @data[b].nil?
        c = a
      else
        c = @data[a] <= @data[b] ? a : b
      end

      if @data[target_idx] > @data[c]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < @data.size
  end
end

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
nks = m.times.map{ gets.split.map(&:to_i) }

pq = PriorityQueue.new(a)
nks.sort_by!{|nk| -nk[1]}
nks.each do |nk|
  q = false
  nk[0].times do
    t = pq.pop
    if t < nk[1]
      pq.push(nk[1])
    else
      pq.push(t)
      q = true
      break
    end
  end
  break if q
end

p pq.sum




Measured memory_bytes: 20108
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t;
int cev;
string s;
vector<int> v;

int main(void){
	cin>>s;
	if(s[0]>='A' && s[0]<='Z')s[0]='A';
	else s[0]='a';
	cout<<s<<endl;
	return 0;
}



Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define N 100007
using namespace std;
char s[N];
int x[N];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    if(s[1]=='0'){puts("-1");return 0;}
    if(s[n]=='1'){puts("-1");return 0;}
    for(int i=1;i<n;++i)
        if(s[i]!=s[n-i]){puts("-1");return 0;}
    int k=0;
    for(int i=1;i<=n;++i)
        if(s[i]=='1')x[++k]=i;
    for(int i=1;i<=k;++i)printf("%d %d\n",i,i+1);
    for(int i=2,id=k+1;i<=k;++i)
        for(int j=x[i]-x[i-1]-1;j>0;--j)printf("%d %d\n",i,++id);
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 1e6+1;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
  if(n >= MAX){
    ll tmp = 1;
    rep(i,k){
      tmp *= (n-i);
      tmp %= MOD;
    }
    return tmp*finv[k]%MOD;
  }

  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll POW(ll x, ll n){
  ll ret = 1;

  if(n < 0){// n < 0 にも対応
    n *= -1;
    x = inv[x];
  }

  while(0 < n){
    if(n%2 == 0){
      x = x*x%MOD;
      n /= 2;
    }
    else{
      ret = ret*x%MOD;
      n--;
    }
  }

  return ret;
}

int n; string s;



//nibutan
bool check(int len){
  map<string,int> C;
  for(int l2 = 0; l2+len <= n; l2++) {
    string t = s.substr(l2,len);
    if(!C.count(t)) C[t] = l2;
    else{
      int l1 = C[t];
      if(l1+len <= l2) return true;
    }
  }
  return false;
}


int main(){
  cin >> n >> s;
  int ok = 0, ng = n/2+1;
  while (abs(ng-ok)>1){
    int mid = (ok+ng)/2;
    if(check(mid)) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}


Measured memory_bytes: 6668
N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])

Measured memory_bytes: 8436