akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+7;
vector<int> vec[N];
int n, m, du[N], dis[N];
int topu_sort()
{
	int res = 0;
	queue<int> q;
	for(int i = 1; i <= n; i++)
	{
		if(!du[i])
		{
			q.push(i);
			dis[i] = 1;
		}
	}
	while(!q.empty())
	{
		int u = q.front();
		for(int i = 0; i < vec[u].size(); i++)
		{
			int v = vec[u][i];
			du[v]--;
			dis[v] = max(dis[v], dis[u]+1);
			if(!du[v])
			{
				q.push(v);
			}
		}
		q.pop();
	}
	for(int i = 1; i <= n; i++)
	{
		res = max(res, dis[i]);
	}
	return res-1;
}
int main()
{
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		du[u]++;
		vec[v].push_back(u);
	}
	printf("%d\n", topu_sort());
	return 0;
}

Measured memory_bytes: 6528
// 幅優先探索
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>

#include<queue>

using namespace std;

#define MAX_N 100
// 値の定義
const int INV = -1;
const int EXIST = 1;
const int NO_EXIST = 0;

// グラフ情報を保持する配列
int ary_graph[MAX_N + 1][MAX_N + 1];

// 頂点１からの距離を保持する配列
int vertex_distance[MAX_N + 1];

int n = 0;

void widthFirstSearch(int start_vertex);

int main(void)
{
    int u, num, v_num;

    for(int i = 0; i < MAX_N + 1; i++)
    {
    	vertex_distance[i] = INV;

        for(int j = 0; j < MAX_N + 1; j++)
        {
            // 配列の初期化
            ary_graph[i][j] = NO_EXIST;
        }
    }

    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> u >> num;

        // 0オリジンにする
        u--;

        for(int j = 0; j < num; j++)
        {
            // 隣接点を記憶する
            cin >> v_num;

            // 0オリジンにする
            v_num--;
            ary_graph[u][v_num] = EXIST;
        }
    }

    // 頂点１から幅優先探索を実施
    widthFirstSearch(0);

    // 結果の表示
    for(int i = 0; i < n; i++)
    {
        printf("%d %d\n", i + 1, vertex_distance[i]);
    }

    return 0;
}

// 幅優先探索を実施する関数
// start_vertex : 起点となる頂点のNo.
// vertex_num : グラフの頂点数
void widthFirstSearch(int start_vertex)
{

    queue<int> Q;

    // 開始点の情報の設定
    Q.push(start_vertex);
    vertex_distance[start_vertex] = 0;

    while( !Q.empty() )
    {
        // キューの先頭要素を取得
        int u = Q.front();
        Q.pop();

        for(int v = 0; v < n; v++)
        {

            if( ary_graph[u][v] == EXIST && vertex_distance[v] == INV )
            {

                // ----- 未訪問の頂点が見つかった -----

                // 距離情報の更新
                vertex_distance[v] = vertex_distance[u] + 1;

                // キューにプッシュする
                Q.push(v);
            }
        }
    }

    return;
}



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

int main() {
    int a[ 3 ] ;
    std::cin >> a[ 0 ] >> a[ 1 ] >> a[ 2 ] ;
    std::sort( a , a + 3) ;
    
    std::cout << a[ 0 ] << " " << a[ 1 ] << " " << a[ 2 ] << std::endl ;
}


Measured memory_bytes: 3144
count = int(input())
numList = list(map(int, input().split()))

ruiseki = [0] * (len(numList) + 1)

for i, num in enumerate(numList):
    ruiseki[i + 1] = ruiseki[i] + num

ruiseki.sort()
ruiseki.append(None)

result = 0

current = ruiseki[0]
count = 1

for wa in ruiseki[1:]:
    if wa != current:
        if count > 1:
            result += count * (count - 1) / 2
        
        current = wa
        count = 1
        continue
    
    count += 1
    
print(int(result))

Measured memory_bytes: 25980
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// Scanner sc = new Scanner(System.in);
		// 整数の入力
		// int a = sc.nextInt();
		// スペース区切りの整数の入力
		// int b = sc.nextInt();
		// int c = sc.nextInt();
		// 文字列の入力
		// String s = sc.next();
		// 出力
		// System.out11.println((a+b+c) + " " + s);

		Scanner sc = new Scanner(System.in);
		int month = sc.nextInt();
		int day = sc.nextInt();

		int count = 0;
		for (int i = 1; i < month; i++) {
			count++;
		}

		if (month <= day) {
			count++;
		}

		System.out.println(count);


	}

}

Measured memory_bytes: 21076
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
const int INF=1e9L+5;
int main()
{
  ll n,k;
  scanf("%lld",&n);
  scanf("%lld",&k);
  vector<ll>h(n);
  for(ll& x: h)
     scanf("%lld",&x);
  vector<ll>dp(n,INF);
  dp[0]=0;
  for(ll i=0;i<n;i++){
    for(ll j=i+1;j<=i+k;j++){
      if(j<n)
        dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
    }
  }
  printf("%lld\n",dp[n-1]);
}

Measured memory_bytes: 1792
import sys
input = sys.stdin.readline


def read():
    A, V = map(int, input().strip().split())
    B, W = map(int, input().strip().split())
    T = int(input().strip())
    return A, V, B, W, T


def solve(A, V, B, W, T):
    is_reached = True
    if A < B:
        a = A + V * T
        b = B + W * T
        is_reached = (a >= b)
    else:
        a = A - V * T
        b = B - W * T
        is_reached = (a <= b)
    return "YES" if is_reached else "NO"


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Measured memory_bytes: 9204
program prob4
    implicit none
    integer :: w, h, n
    integer, allocatable :: x(:), y(:), a(:)
    integer :: i, j, k, ans
    logical :: check
    read(*,*) w, h, n
    allocate(x(n), y(n), a(n))
    do k = 1, n
        read(*,*) x(k), y(k), a(k)
    end do
    ans = 0
    do i = 1, W
        do j = 1, H 
            check = .true.
            do k = 1, N
                if(a(k) == 1) then
                    if(i <= x(k)) then
                        check = .false.
                    end if
                else if(a(k) == 2) then
                    if(i-1 >= x(k)) then
                        check = .false.
                    end if
                else if(a(k) == 3) then
                    if(j <= y(k)) then
                        check = .false.
                    end if
                else
                    if(j-1 >= y(k)) then
                        check = .false.
                    end if
                end if
            end do
            if(check .eqv. .true.)then
                ans = ans + 1
            end if
        end do
    end do
    write(*,*) ans

    deallocate(x, y, a)

    stop
contains
end program prob4

Measured memory_bytes: 2800
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll N;
    cin >> N;
    vector<ll> A(N),D(N);
    ll sum = 0;
    rep(i,N){
        cin >> A[i];
        sum += A[i];
    }
    ll b = (N+1)*N/2;
    if(sum % b != 0 ){
        cout << "NO" << endl;
        return 0;
    }
    ll k = sum / b;
    rep(i,N){
        D[i] = A[(i+1)%N] - A[i] - k;
    }
    ll cnt = 0;
    rep(i,N){
        if(D[i]% N!=0){
            cout << "NO" << endl;
            return 0;
        }else cnt += abs(D[i])/N;
    }
    if(cnt==k)cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N, X;
    ll ans;
    cin >> N >> X;
    cin >> ans;
    ans -= X;
    rep(i, N - 1) {
        ll temp;
        cin >> temp;
        ans = __gcd(ans, temp - X);
    }
    cout << abs(ans) << endl;
    return 0;
}


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

int main()
{
    int n,k;
    cin >> n >> k;
    int l[n],ans = 0;
    for(int i = 0; i < n; i++) cin >> l[i];

    sort(l,l+n,greater<int>());
    
    for(int i = 0; i < k; i++) ans += l[i];

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    sc.nextLine.toInt
    val s = sc.next
    println(s.scanLeft(0) {
      case (a, b) if b == 'I' => a + 1
      case (a, b) if b == 'D' => a - 1
    }.max)
  }
}


Measured memory_bytes: 25924
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
	T res = 1;
	for(;n;n>>=1) {
		if (n & 1) res = res * a;
		a = a * a;
	}
	return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
	 return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
	 os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
	for(auto const& x:{args...}){
		cerr<<x<<' ';
	}
	cerr<<ENDL;
}



signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	db a,b,h,m;cin>>a>>b>>h>>m;


	ll tm=60*h+m;

	db t1=(db(tm%720)/720)*(2.0*acos(-1.0));
	db t2=(db(tm%60)/60)*(2.0*acos(-1.0));
	cerr<<t1<<" "<<t2<<ENDL;

	cout<<sqrt(pow(a*cos(t1)-b*cos(t2),2)+pow(a*sin(t1)-b*sin(t2),2))<<ENDL;


}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

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

  rep(i, S.size()) {
    cout << "x";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
M,K=gets.chomp.split(' ').map{|n| n.to_i}
if(K>=2**M)
	puts -1
	exit(0)
end
if(M==0)
	puts "0 0"
	exit(0)
elsif(M==1&&K==0)
	puts "0 0 1 1"
	exit(0)
elsif(M==1&&K==1)
	puts "-1"
	exit(0)
end
print "#{K} "
for i in 0..(K-1)
	print "#{i} "
end
for i in (K+1)..(2**M-1)
	print "#{i} "
end
print "#{K} "
(2**M-1).downto(K+1){|i|
	print "#{i} "
}
(K-1).downto(0){|i|
	print "#{i} "
}
puts ""


Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int fib(int a){
    int b=0;
    if(a==1){
        return 1;
    }
  else if(a==2){
    return 2;
  }
    else{
        b=+(fib(a-1)+fib(a-2));
        return b;
    }
}
int main(){
  ll n;
  cin>>n;
  vector<pair<ll,ll>> work;
  for(int i=0;i<n;i++){
    ll a,b;
    cin>>a>>b;
    work.emplace_back(b,a);
  }
  sort(begin(work),end(work));
  ll time=0,ans=0;
  for(ll i=0;i<n;i++){
    ll memo1,memo2;
    memo1=get<1>(work[i]);
    memo2=get<0>(work[i]);
    time+=memo1;
    if(time>memo2){
      ans++;
      break;
    }
  }
  if(ans==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 6384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		if(N == 1) {
			System.out.println("Hello World");
		}else {
			int A = scan.nextInt();
			int B = scan.nextInt();
			System.out.println(A + B);
		}
		scan.close();
	}
}

Measured memory_bytes: 23636
#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define DEBUG(x) cerr << #x << ": " << x << "\n"

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int n;
    cin >> n;
    cout << 1110 - n << endl;
    return 0;
}


Measured memory_bytes: 256
#include <map>
#include <cstdio>
using namespace std;
#define ll long long
ll h;
map<ll,ll> d;
ll getans(ll h){
	if (h==1){
		return d[h]=1;
	}
	if (d[h]!=0){
		return d[h];
	}
	return d[h]=2*getans(h/2)+1;
}
int main(){
	scanf("%lld",&h);
	printf("%lld",getans(h));
	return 0;
}


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

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 1000;
char s[N+3][N+3];
int a[N+3];
int len[N+3];
char t[N+3];
int n;

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {scanf("%s%d",s[i]+1,&a[i]); len[i] = strlen(s[i]+1);}
	scanf("%s",t+1); int lent = strlen(t+1);
	int ans = 0;
	for(int i=n; i>=1; i--)
	{
		if(lent==len[i])
		{
			bool ok = true;
			for(int j=1; j<=lent; j++) {if(s[i][j]!=t[j]) {ok = false; break;}}
			if(ok) {break;}
		}
		ans += a[i];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long m[100001][101];
int w[101];
long long v[101];
int n,W;
long long dp(int s,int i){
	if(i==n) return 0;
	if(s==0) return 0;
	if(m[s][i]!=-1) return m[s][i];
	m[s][i]=dp(s,i+1);
	if(s>=w[i]){
		m[s][i]=max(m[s][i],dp(s-w[i],i+1)+v[i]);
	}
	return m[s][i];
}
int main(){
	scanf("%d%d",&n,&W);
	for(int i=0;i<n;i++){
		scanf("%d%lld",&w[i],&v[i]);
	}	
	memset(m,-1,sizeof(m));
	cout<<dp(W,0);
}

Measured memory_bytes: 79104
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


INT_MAX = 10 ** 10


if __name__ == "__main__":
    N, K = readmap()
    S = input()

    happynum = sum([S[i] == S[i-1] for i in range(1, N)])
    print(min(happynum + 2 * K, N - 1))



Measured memory_bytes: 4596
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int MAX = 5e6;
const int MOD = 1e9+7;

int memo[MAX];

int fra(int a){ // a! % MODを返す
  // いちいち計算し直すのは大変なのでメモしておこう
  if( a <= 0 ){ return 1;}
  if( memo[a] != -1 ){ return memo[a];}
  
  return memo[a] = ( fra(a-1)*a ) % MOD;
}

int powe(int a, int b){ // a^b%MODを返す
 
  if( b == 0 ){ return 1LL;}
  else if( b == 1 ){ return a%MOD;}
  
  if( b % 2 == 0 ){ return ( powe(a,b/2)*powe(a,b/2) ) % MOD;}
  else{
    return ( ( ( powe(a,(b-1)/2 )*powe( a,(b-1)/2 ) )%MOD )*a )%MOD;
  }
}
    
  

signed main(void){
  
  int N,A,B,C; cin >> N >> A >> B >> C;
  
  for(int i = 0; i < MAX; i++){ memo[i] = -1;}
  memo[0] = 1; memo[1] = 1; memo[2] = 2; memo[3] = 6;
  fra(MAX-1);
  
  int ans = 0;
  
  for(int M = N; M < 2*N; M++){ 
    
    int nume = fra(M-1);
        nume *= (100*M)%MOD;
        nume %= MOD;
    
    int res = (powe(A,N)*powe(B,M-N))%MOD + (powe(A,M-N)*powe(B,N))%MOD;
        res %= MOD;
        nume *= res; 
        nume %= MOD;
    
    int deno = ( fra(N-1) * fra(M-N) ) % MOD;
        res = powe(A+B,M);
        deno *= res;
        deno %= MOD;
        deno *= (100-C);
        deno %= MOD;
    
        nume *= powe(deno,MOD-2);
        nume %= MOD;
    
    ans += nume;
    ans %= MOD;
  }
  
  cout << ans << endl;
  
  return 0;
} 

Measured memory_bytes: 117376
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXA 1001
#define MAXB 1001
#define MAXH 1000000001
#define MAXW 301
#define INF (1LL << 50)
#define MAXN 100001
#define MAXM 100001
#define MAXK 100002
#define MAXP 1000001
#define MOD 1000000007
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

string s;
int N;

int main(){
    cin >> N >> s;
    stack<char> ss;
    string ans = "";
    for(int i = s.length() - 1;i >= 0;i--){
        if(s[i] == '(' && !ss.empty() &&ss.top() == ')'){
            ss.pop();
        }else ss.push(s[i]);
    }


    while(!ss.empty() && ss.top() == ')'){
        ans += "(";
        ss.pop();
    }
    ans += s;
    while(!ss.empty()){
        ans += ")";
        ss.pop();
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
import math

def insertion_sort(a, n, g):
    ct = 0
    for j in range(0,n-g):
        v = a[j+g]
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j-g
            ct += 1
        a[j+g] = v
    return ct

n = int(input())
a = list(map(int, sys.stdin.readlines()))
b = 701
ct= 0
g = [x for x in [1,4,10,23,57,132,301,701] if x <= n]
while True:
    b = math.floor(2.25*b)
    if b > n:
        break
    g.append(b)
g = g[::-1]

for i in g:
    ct += insertion_sort(a, n, i)

print(len(g))
print(*g, sep=" ")
print(ct)
print(*a, sep="\n")

Measured memory_bytes: 118612
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    ll n,m; cin >>n>>m;
    vector<ll> x(n); rep(i,n) cin >> x[i];
    vector<ll> y(m); rep(i,m) cin >> y[i];

    ll h_ans = 0;
    for (ll i = 1; i < n; i++) {
        ll s = (x[i] - x[i-1]);
        s %= MODLL;
        s *= i;
        s %= MODLL;
        s *= (n-i);
        s %= MODLL;
        h_ans += s;
        h_ans %= MODLL;
    }

    ll ans = 0;
    for (ll i = 1; i < m; i++) {
        ll ss = (y[i] - y[i-1]);
        ss %= MODLL;
        ss *= i;
        ss %= MODLL;
        ss *= (m-i);
        ss %= MODLL;
        ans += ss;
        ans %= MODLL;
    }

    ans *= h_ans;
    ans %= MODLL;
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 1792
def inpl(): return list(map(int, input().split()))

N, x = inpl()
a = inpl()
a = sorted(a)
ans = 0
for ai in a:
    if x>=ai:
        x -= ai
        ans += 1
    else:
        break
else:
    if x!=0:
        ans -= 1
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>

int main(void){
	int a,b,c,d,l;
	scanf("%d%d%d%d%d",&l,&a,&b,&c,&d);
	a=(a-1)/c;
	b=(b-1)/d;
	a++;
	b++;
	if(a>b){
		l-=a;
	}else{
		l-=b;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main() {
	int n, x, y, l, r;
	scanf("%d%d%d%d%d", &n, &x, &y, &l, &r);
	long long delta = y - x;
	n--;
	for(int i = 0; i <= n; i++) {
		long long li = 1LL * i * l - 1LL * (n - i) * r, ri = 1LL * i * r - 1LL * (n - i) * l;
		if(li <= delta && delta <= ri) {
//			printf("%lld %lld\n", li, ri);
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

		public static void main(String[] args){
			Scanner sc = new Scanner(System.in);
			int a = sc.nextInt();
			int b = sc.nextInt();
			if((1 <= a && b <= 10000) && (a * b % 2 == 1)) {
				System.out.println("Odd");}
			else if((1 <= a && b <= 10000) && (a * b % 2 == 0)) {
				System.out.println("Even");
			}}}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)
using Graph = vector<vector<int>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll n;
  cin>>n;
  ll arr[n];
  fr(i,n){
    ll b;
    cin>>b;
    arr[b-1]=i;
  }
  ll ans,x;
  x=0;
  ans = 0;
  fr(i,n-1){
    if(arr[i]<arr[i+1]){
      ++x;
    }
    else{
      ans=max(ans,x);
      x=0;
    }
  }
  ans=max(ans,x);
  cout<<n-ans-1;
}

Measured memory_bytes: 1920
# -*- coding: utf-8 -*-
N = int(input())
S = [0,0]
index = 0

for i in range(N):
	A = int(input())
	if A > S[0]:
		S[1] = S[0]
		S[0] = A
		index = i
	elif A > S[1]:S[1] = A

for i in range(N):
	if i != index:
		print(S[0])
	else:
		print(S[1])


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

int main()
{
    int a,b,c,x,y,ans;
    cin>>a>>b>>c>>x>>y;
    ans=0;
    if(a+b>c*2)
    {
        int m=min(x,y),num,price;
        ans+=m*2*c;
        x-=m,y-=m;
        price=x==0?b:a;
        num=max(x,y);
        
        if(price>c*2)
            ans+=num*2*c,x=0,y=0;
    }
    
    ans+=x*a+y*b;
    
    cout<<ans<<endl;
    
    return 0;
}



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

P2 = P.copy()
P2.sort()
cnt = 0
for i in range(N):
    if P[i]==P2[i]:
        cnt += 1
if cnt==N or cnt==N-2:
    print("YES")
else:
    print("NO")

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<string> S;
int ret;
int R[501],C[501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(y,N) {
		cin>>s;
		S.push_back(s);
		FOR(x,N) if(S[y][x]=='#') R[y]++, C[x]++;
	}
	
	if(count(R,R+N,0)==N) return _P("-1\n");
	
	int mi=101010;
	FOR(y,N) {
		int num=0;
		int add=0;
		FOR(x,N) if(S[y][x]=='.') num++;
		FOR(i,N) if(S[i][y]=='#') add=1;
		if(num && add==0) num++;
		FOR(x,N) if(C[x]!=N) num++;
		mi=min(mi,num);
	}
	
	cout<<mi<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 512
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        List<String> strListOdd = Arrays.asList("R", "U", "D");
        List<String> strListEven = Arrays.asList("L", "U", "D");
        for (int i = 0; i < S.length(); i++) {
            String c = String.valueOf(S.charAt(i));
            if ((i % 2 == 0) && !strListOdd.contains(c) || (i % 2 == 1) && !strListEven.contains(c)) {
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");
    }
}

Measured memory_bytes: 22996
s = input()
s_set = set(s)
def shrink(r,s):
    s = list(s)

    t = 0
    while True:

        if len(set(s)) == 1:
            break
        else:
            t += 1

        new_s = []
        for i in range(len(s)-1):
            if s[i] == r or s[i+1] == r:
                new_s.append(r)
            else:
                new_s.append(s[i])
        s = new_s
    return t

ans_list = [ shrink(i,s) for i in s_set]
print(min(ans_list))

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

int main() {
	long long A, B; cin >> A >> B;
	for (long long  i = 1; i <= 1e18; i++)
	{
		if (A * i % B == 0) {
			cout << A * i << endl;
			break;
		}
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib> //abs() for integer
#include<cmath> //abs() for float, and fabs()
using namespace std;
int main(){
    int N;
    cin >> N;
    int A[N];
    for(int i = 0; i < N; i++) cin >> A[i];
    int m = 0, min = 1e+9;
    long sum = 0;
    for(int i = 0; i < N; i++){
        if(A[i] < 0) m++;
        if(abs(A[i]) < min) min = abs(A[i]);
        sum += abs(A[i]); //桁落ちは考えなくてもよいのか．．．
    }
    if(m % 2 != 0) sum -= 2 * abs(min);

    cout << sum << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(void){
  int S, W;
  cin >> S >> W;
  if(W >= S){
    cout << "unsafe" << endl;
  }
  else{
    cout << "safe" << endl;
  }

}

Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include <cmath>

using namespace std;




int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(1) {
    int r0,w,c,r;
    cin >> r0 >> w >> c >> r;
    if(r0 == 0 & w == 0 && c == 0 && r == 0) break;
    if(r0 / w >= c) {
      cout << "0" << endl;
    } else {
      int tmp = (c - r0)/ r;
      for(int i = tmp - 10; ; i++) {
        if((r0 + i * r) / w >= c) {
          cout << i << endl;
          break;
        }
      }
    }
  }

}






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

#define vd vector<double>
 
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define vc vector<char>
#define vcc vector< vector<char> >
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
// #define mp make_pair
//#define endl '\n'
 
int main() {
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    int ans = 0;
	rep(r,N+1){
        rep(g,N+1){
            int v = N - r * R - g * G;
            if(v >= 0 && v % B == 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int t = sc.nextInt();

        int d = (int)Math.ceil((double)n/(double)x);
        System.out.println(d*t);
    }
}


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

vector<int> ans;
int N;
int main(){
    cin >> N;
    vector<int> v(N+1);
    bool judge = true;
    for(int i=1;i<=N;i++){
        cin >> v[i];
        if(v[i]>i) judge = false;
    }
    if(!judge){
        cout << -1 << endl;
        return 0;
    }
    while(v.size()>1){
        for(int i=v.size()-1;i>=1;i--){
            if(v[i]==i){
                ans.push_back(i);
                v.erase(v.begin()+i);
                break;
            }
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout << x << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CLEAR(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



vector<int> sq;
const int MAX = 1 << 15;
int c[MAX];
void recur(int num, int after, int sum)
{
	if (sum >= MAX)
		return;
	else if (sum)
	{
		++c[sum];
		if (num == 0)
			return;
	}

	for (int i = after; i < sq.size(); ++i)
		recur(num - 1, i, sum + sq[i]);
}
int main()
{
	for (int i = 1; i * i < MAX; ++i)
		sq.push_back(i * i);

	recur(4, 0, 0);

	int n;
	while (scanf("%d", &n), n)
		printf("%d\n", c[n]);
}

Measured memory_bytes: 920
# ABC 140

N = int(input())
A = [int(a)-1 for a in input().split()]
B = [int(a) for a in input().split()]
C = [int(a) for a in input().split()]
m =0
l = N + 10
for a in A:
    m+=B[a]
    if l+1 == a:
        m+=C[l]
    l=a
print(m)

Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func main() {
  var C1, C2 string 
  fmt.Scanf("%s", &C1)
  fmt.Scanf("%s", &C2)
  
  ans := "YES"
  for i := 0; i < len(C1); i++ {
    if C1[i] != C2[len(C2)-1-i] {
      ans = "NO"
      break;
    }
  }

  fmt.Printf("%s\n",ans)
}

Measured memory_bytes: 1832
n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

a = 0
for i in range(n - 2):
    d = 1
    while True:
        j = i + d
        k = j + d
        if k >= n:
            break

        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            a += 1

        d += 1

print(r*g*b - a)


Measured memory_bytes: 9204
a, b, c = map(int, input().split())
if a * c <= b:
    print(c)
if a * c > b:
    print(b // a)
#h
#
#
#
# e
# d
# h
# h
# r
# h
# b
# h
# cr
# h
# c
# b
# r
# y
# c
# y
# e
# g
# y
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
# e

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

#define ll long long
#define ull unsigned long long

#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

#define INDEX(width, x, y) ((width) * (y) + (x))

bool isPalindrome(string s) {
    string t(s.rbegin(), s.rend());
    return s == t;
}

int main(void) {
    ll N, M;
    cin >> N >> M;
    if(N == 1 && M == 1) {
        cout << 1 << endl;
    } else if(N == 1 || M == 1) {
        cout << N * M - 2 << endl;
    } else {
        cout << (N - 2) * (M - 2) << endl;
    }
    return 0;
}


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

using namespace std;

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

int main(void) {
  int n, x;
  cin >> n >> x;
  vector<int> X(n);
  for (int i = 0; i < n; i++) { cin >> X[i]; }
  X.push_back(x);
  std::sort(X.begin(), X.end());

  int xmin = X[0];
  vector<int> xdiff;
  for (int i = 1; i < n + 1; i++) {
    xdiff.push_back(X[i] - xmin);
  }

  int D = xdiff[0];
  for (int i = 1; i < xdiff.size(); i++) {
    D = gcd(D, xdiff[i]);
  }
  cout << D << endl;
}


Measured memory_bytes: 1528
s, t = [list(input()) for _ in range(2)]

s.sort()
ss = "".join(s)

t.sort(reverse=True)
tt = "".join(t)

if ss == tt:
  print("No")
  exit()

li=[ss, tt]
li.sort()

if li[0] == ss:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include"iostream"
#include"algorithm"
using namespace std;

int main(){
  int n;
  long a[3]={-1};
  int MAX;
  cin>>n;
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  MAX=a[0];
  if(MAX<a[1])MAX=a[1];
  if(MAX<a[2])MAX=a[2];
  for(int i=1;i<MAX;++i){
    for(int j=0;j<n;++j){
      if(a[j]%i!=0)break;
      if(j==n-1)cout<<i<<endl;
    }
  }
  return 0;
}



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

int main(){
  int i,j,cnt=0;
  int n;
  cin>>n;
  int a[n];
  for(i=0;i<n;i++)cin>>a[i];
  for(i=1;i<n;i++){
    if(a[i]==a[i-1]){
      cnt++;
      i++;
    }
  }
  cout<<cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int main()
{
    ll n,k;
    cin >>n>>k;
    ll ans=0;
    while(k<=n)
    {
        ll res=(k*(n-k+1+n)/2-k*(k-1)/2+1+mod)%mod;
        ans=(ans+res)%mod;
        k++;
    }
    ans++;
    cout <<ans%mod<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    set<ll> st;
    vl v(n+1);  // v[i] : i問目をACしたら1
    vl cnt(n+1);  // cnt[i] : i問目でWAを出した回数
    rep(i, m) {
        ll p;
        string s;
        cin >> p >> s;
        if(s == "AC") {
            st.insert(p);
            v[p] = 1;
        }
        else {
            if(v[p] == 0) {
                cnt[p]++;
            }
        }
    }

    out(st.size());

    ll ans = 0;
    exrep(p, 1, n) {
        if(v[p]) {
            ans += cnt[p];
        }
    }

    out(ans);
    re0;
}

Measured memory_bytes: 6528
import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int X;
		int N;

		X = scan.nextInt();
		N = scan.nextInt();

		int p[] = new int[N];

		Set<Integer> inputSet = new HashSet<Integer>();

		for (int i = 0; i < N; i++) {
			inputSet.add(scan.nextInt());
		}

		//Xから見てループしていく
		//大きいのと、小さいの交互にみていく
		int ans;
		int radius = 0;

		while (true) {
			if (inputSet.contains(X + radius)) {
				//リストに含んでいるとき
			} else {
				//リストにいないとき
				//答えに入れる
				ans = X + radius;

				break;
			}

			if (radius > 0) {
				//差が正数の時はマイナス側を確認
				radius *= -1;
			} else {
				//マイナスの時は次の正数を確認
				radius *= -1;
				radius++;
			}

		}

		if (radius > 0) {
			//最後に見たのが正数側の時は負数側も確認する
			radius *= -1;

			if (!inputSet.contains(X + radius)) {
				//いなければ答えを書き換える
				ans = X + radius;
			}
		}

		System.out.println(ans);

	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 27220
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <ios>
using namespace std;
int main(void){
  long N,M;
  cin >> N >> M;

  vector<pair<long,long> >drink(N);

  for(int i=0;i<N;i++){
    cin >> drink[i].first;
    cin >> drink[i].second;
  }

  /*for(int i=0;i<N;i++){
    cout << drink[i].first << " " << drink[i].second << endl;
  }
  */

  sort(drink.begin(),drink.end());

  long ans = 0;
  long shop = 0;

  while(M > 0 && shop < N){
    long drink_buy = min(M,drink[shop].second);
    M -= drink_buy;
    ans += drink_buy * drink[shop].first;
    shop++;
  }

  cout << ans << endl;

  return 0;
}

  
  

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    string s;
    cin>>n>>s;
    vector<vector<int>> vec(10);
    rep(i,n) {
        vec[s[i]-'0'].push_back(i);
    }
    rep(i,10) vec[i].push_back(INF);
    
    int ans=0;
    rep(i,10) {
        int pos=vec[i][0];
        if(pos==INF) continue;
        rep(j,10) {
            int pos2=*upper_bound(all(vec[j]),pos);
            if(pos2==INF) continue;
            rep(k,10) {
                int pos3=*upper_bound(all(vec[k]),pos2);
                if(pos3==INF) continue;
                //cout<<pos<<" "<<pos2<<" "<<pos3<<endl;
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {

	int n;
	cin >> n;
	if (n == 1)
		cout << "Hello World" << endl;
	else {
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <queue>

char cmd[10];
std::priority_queue<int> pque;

int main()
{
    while( scanf( "%s", cmd ), strcmp( cmd, "end" ) )
    {
        if( !strcmp( cmd, "insert" ) )
        {
            int k;
            scanf( "%d", &k );

            pque.push( k );
        }
        else
        {
            printf( "%d\n", pque.top() ); 
            pque.pop();
        }
    }

    return 0;
}

Measured memory_bytes: 6564
S = input()
Q = int(input())

forward = True
que0 = []
que1 = []

for _ in range(Q):
    query = input().split()

    if query[0] == '1':
        forward = not forward

    else:
        head = (query[1] == '1')
        if head ^ forward:
            que1.append(query[2])
        else:
            que0.append(query[2])

S = ''.join(que0[::-1]) + S + ''.join(que1)

if forward:
    print(S)
else:
    print(S[::-1])

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

using namespace std;

int main()
{
    int h, m, s;
     
    while (cin >> h >> m >> s, h >= 0) {
        int tl = (3600 * 2) - (3600 * h + 60 * m + s), tri = tl * 3;
        printf("%02d:%02d:%02d\n", tl/60/60, tl/60%60, tl%60);
        printf("%02d:%02d:%02d\n", tri/60/60, tri/60%60, tri%60);
    }
    return 0;
}

Measured memory_bytes: 3072
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

S = input()
T = input()

ans = 0
for s, t in zip(S, T):
    if s != t:
        ans += 1
print(ans)



Measured memory_bytes: 9688
#include<map>
#include<iostream>

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

using ll = long long;
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string,int> mp;
    rep(i,n) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        mp[s]++;
    }
    ll ans = 0;
    for (auto& p : mp) {
        int s = p.second;
        ans += (ll)s*(s-1)/2;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  
  int x, N, K;
  cin >> N >> K;
  x = 1;
  for (int i = 0; i<N; i++) {
    if (x<K) x *= 2;
    else x += K;
  }
  
  cout << x << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[7];
int main()
{
    int i,j,k,m,n;
    while(cin>>a)
    {
        int count=0;
        for(i=0;i<strlen(a);i++)
        {
            if(a[i]=='1')
                count++;
        }
        cout<<count<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int input;
  cin >> input;
  int A = input /1000;
  int B = input /100 - A * 10;
  int C = input /10 - A * 100 - B * 10;
  int D = input  - A * 1000 - B * 100 - C * 10;
  if(A + B + C + D == 7) cout << A << "+" << B << "+" << C << "+" << D << "=" << 7 << endl;
  else if(A - B + C + D == 7) cout << A << "-" << B << "+" << C << "+" << D << "=" << 7 << endl;
  else if(A + B - C + D == 7) cout << A << "+" << B << "-" << C << "+" << D << "=" << 7 << endl;
  else if(A + B + C - D == 7) cout << A << "+" << B << "+" << C << "-" << D << "=" << 7 << endl;
  else if(A - B - C + D == 7) cout << A << "-" << B << "-" << C << "+" << D << "=" << 7 << endl;
  else if(A - B + C - D == 7) cout << A << "-" << B << "+" << C << "-" << D << "=" << 7 << endl;
  else if(A + B - C - D == 7) cout << A << "+" << B << "-" << C << "-" << D << "=" << 7 << endl;
  else if(A - B - C - D == 7) cout << A << "-" << B << "-" << C << "-" << D << "=" << 7 << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;cin>>n;
  string s = to_string(n);
  int nw = 10;
  long long ans = 0;
  for(int i = 1; s.size() >= i; i+=2){
   	if(i == s.size()){
      ans += n - nw/10+1;
      //cerr << n << " " << nw+1 << endl;
    }else{
      ans += nw - (nw/10);
      //cerr << nw << endl;
    }
    nw *= 100;
  }
  cout << ans << endl;
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int f(int a) {
  return (a * a + 4) / 8;
}

ll memo[1000];
ll fib(ll n) {
  if(n == 0) return 2;
  else if(n == 1) return 1;
  else if(memo[n]) return memo[n];
  else return memo[n] = fib(n-1) + fib(n-2);
}

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

  int n; cin >> n;
  int x = n, y = 0;
  while(n > 0) {
    y += n % 10;
    n /= 10;
  }
  cout << (x %  y ? "No" : "Yes") << endl;
  
}


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

int a[31];

int main()
{
  int n, m = 28;

  while (m--){
    cin >> n;
    a[n]++;
  }
  for (int i = 1; i <= 30; i++){
    if (a[i] == 0){
      cout << i << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1164
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
static const double EPS = 1e-8;
typedef long long ll;

int N, M;
double L[20], a[20], b[20];
double dp[1 << 20];

double sq(double n)
{
	return n*n;
}
template <class T>
T next_combination(T combi)
{
	T leastBit = combi & -combi;
	T mostBits = combi + leastBit;
	T leastSequentialBits = combi & ~mostBits;
	return mostBits | ((leastSequentialBits / leastBit) >> 1);
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i)
		scanf("%lf %lf %lf", L+i, a+i, b+i);

	double ans = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 1; j < M && j < N; ++j)
		{
			for (int bits = (1 << j) - 1; bits < 1 << i; bits = next_combination(bits))
			{
				dp[(1 << i) + bits] = dp[bits];
				for (int k = 0; 1 << k <= bits; ++k)
					if (bits & 1 << k)
						dp[(1 << i) + bits] += sq(L[k]-L[i]) + sq(a[k]-a[i]) + sq(b[k]-b[i]);
				if (dp[(1 << i) + bits] > ans)
					ans = dp[(1 << i) + bits];
			}
		}
	}
	printf("%.20f\n", ans);

	return 0;
}

Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  for (int i = 0; i < s.size(); i++) {
    s[i] = 'x';
  }

  cout << s << endl;

  return 0;
}

Measured memory_bytes: 256