akhauriyash/Code-Regression huggingface dataset:
N = int(input())

words = []

flag = 0

for i in range(N):
    w = input()
#    print(words)
    words.append(w)
    if i == 0:
        continue
    if words[i-1][-1] != w[0]:
        flag = 1

sets = set(words)

if len(sets) != len(words):
    flag = 1

if flag == 1:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 3060
n = int(input())

ai = [int(i) for i in input().split()]

ai_li = []

for i in range(n):
    ai_li.append([ai[i],i+1])

ai_li.sort(reverse=True)

dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    #print(i)
    for j in range(0,i+1):
        if i == 1:
            if j == 1:
                dp[i][j] = ai_li[i-1][0]*abs(ai_li[i-1][1]-1)
            else:
                dp[i][j] = ai_li[i-1][0]*abs(n-ai_li[i-1][1])
        else:
            if j == 0:
                #print(dp[i][j])
                dp[i][j] = dp[i-1][0] + ai_li[i-1][0]*abs(n-ai_li[i-1][1]-i+1)
            else:
                #if i == 2:
                #    print(i-1,j-1)
                dp[i][j] = max(dp[i-1][j-1]+ai_li[i-1][0]*abs(ai_li[i-1][1]-j),dp[i-1][j]+ai_li[i-1][0]*abs(n-ai_li[i-1][1]-(i-1-j)))
                #dp[i][j] = max(dp[i-1][j-1]+ai_li[i][0]*abs(ai_li[i][1]-1+i-1),dp[i-1][j]+ai_li[i][0]*abs(n-i+1-ai_li[i][1]))

#print(dp)
print(max(dp[n]))

Measured memory_bytes: 102044
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  int N, M;
  int res=0;
  cin >> N >> M;

  res += N*(N-1)/2;
  res += M*(M-1)/2;

  cout << res << endl;
}


Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
#include <numeric>
#include <bitset>
#include <map>
#include <limits.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<=n;i++)
using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;


/// 各桁の和
int sumdigit(int x){
   int sum = 0;
    while(x != 0){
        sum += x % 10;
        x /= 10;    
    }
    return sum;
}
/// 最大公約数 
int gcd(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }
      int r = x % y;
       while(r!=0){
           x = y;
           y = r;
           r = x % y;
       }
      return y;
   }



int main(){
   int N;
   cin >> N;
   string S;
   cin >> S;
   int cntr = 0;
   int cntb = 0;
   REP(i,N){
       if(S[i] == 'R'){
           cntr++;

       }
       else{
           cntb++;

       }
   }
   if(cntr > cntb)cout << "Yes" << endl;
   else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

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

	// pair<整数, 個数>
	// Aiは個数1で格納
	priority_queue<pair<int, int>> Q;
	for (int i = 0; i < N; i++)
	{
		int A;
		cin >> A;
		Q.push(pair<int, int>(A, 1));
	}
	// <Cj, Bj>
	for (int j = 0; j < M; j++)
	{
		int B, C;
		cin >> B >> C;
		Q.push(pair<int, int>(C, B));
	}

	// priority_queueから1つずつ取り出してansに足し、
	// 個数が1個より多ければ個数をデクリメントして再度格納
	// O(logN)
	ll ans = 0;
	for (int i = 0; i < N; i++)
	{
		auto p = Q.top();
		Q.pop();
		ans += p.first;
		if (p.second > 1)
		{
			p.second--;
			Q.push(p);
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 2420
import java.util.*;
import java.lang.*;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		long n = sc.nextLong();
        BigInteger count = BigInteger.ONE;
      	long z = (long)Math.pow(10, 18);
      	BigInteger check = BigInteger.ONE;
      	check = check.multiply(BigInteger.valueOf(z));
        int i;
      	
        try{
      		for(i = 0;i < n; i++){
              count = count.multiply(BigInteger.valueOf(sc.nextLong()));
              	//10の18乗を超えた時
            	if(count.compareTo(check) > 0){
                  	//強引にキャッチさせる構文にする
                  	for(i = 0;i <= n ; i++){
                      if(sc.nextLong() == 0){
                        System.out.println(0);
              		    System.exit(0);                        
                      }
                    }
       			 }
        	}
        }catch (NoSuchElementException e){
            System.out.println(-1);
          	System.exit(0);
        }

      	 System.out.println(count);
    }
}

Measured memory_bytes: 60828
import java.util.*;
class Main{
    int min(int a,int b){
	if(a<b)return a;
	else return b;
    }
    int max(int a,int b){
	if(a>b)return a;
	else return b;
    }
    Main(){
	Scanner sc =new Scanner(System.in);
	while(true){
	    int a=sc.nextInt();
	    int b=sc.nextInt();
	    int c=sc.nextInt();
	    if(a==0&&b==0&&c==0)break;
	    int n=sc.nextInt();
	    int x=min(a*a+b*b,min(a*a+c*c,b*b+c*c));
	    for(int i=0;i<n;i++){
		String Ans="NA";
		int r=sc.nextInt();
		r*=2;
		if(r*r>x)Ans="OK";
		System.out.println(Ans);
	    }
	}

    }
    public static void main (String[]arg){
	new Main();
    }
}

Measured memory_bytes: 17200
#include <iostream>
#include <math.h>
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <utility> //pair
#include <algorithm> //sort
using namespace std;


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

    sort(S.begin(), S.end());
    //cout << S << endl;
    if (S[0] == S[1] and S[1] != S[2] and S[2] == S[3]) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
typedef long long ll;
using namespace std;
int main(){
    IOS;
    vector<int>v(5);
    for(int i=0;i<5;i++) cin>>v[i];
    auto it=find(v.begin(),v.end(),0);
    cout<<it-v.begin()+1<<endl;
}

Measured memory_bytes: 3644
#設定
import sys
input = sys.stdin.buffer.readline
import bisect

INF = float("inf")

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	X = getlist()
	X.append(INF)
	L = int(input())
	double = [[0] * (N + 1) for i in range(20)]
	for i in range(N):
		p = bisect.bisect_left(X, X[i] + L + 1)
		double[0][i] = p - 1
	for i in range(20):
		double[i][N] = INF
	
	for i in range(1, 20):
		for j in range(N):
			double[i][j]  = double[i - 1][double[i - 1][j]]

	# for i in range(5):
	# 	print(double[i])

	Q = int(input())
	for i in range(Q):
		a, b = sorted(getlist())
		a -= 1; b -= 1
		ans = 0
		for j in range(20):
			if double[19 - j][a] < b:
				a = double[19 - j][a]
				ans += 1 << (19 - j)

		print(ans + 1)

if __name__ == '__main__':
	main()

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

int main()
{
	int n, p, m = 0, s = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> p;
		if (p > m)
			m = p;
		s += p;
	}

	cout << s - m / 2 << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, T; cin >> N >> T;
    vector<int> cnt(T + 1, 0);
    for(int i = 0; i < N; i++)
    {
        int l, r; cin >> l >> r;
        cnt[l]++;
        cnt[r]--;
    }
    for(int i = 1; i <= T; i++) cnt[i] += cnt[i - 1];
    int ans = 0;
    for(int i = 0; i <= T; i++) ans = max(ans, cnt[i]);
    cout << ans << endl;
    return 0;
}




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

int a=0,n,x;

int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        if(x%2==0){
            if(x%3==0||x%5==0)continue;
            else a++;
        }
        
    }
    if(a)cout<<"DENIED\n";
    else cout<<"APPROVED\n";
    
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    minDiff = 10 ** 18
    for i in range(N - K + 1):
        minDiff = min(minDiff,h[i+K - 1] - h[i])
    print(minDiff)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    q = []
    for i in range(N):
        q.append(int(next(tokens)))
    q.sort()
    solve(N, K, q)

if __name__ == '__main__':
    main()


Measured memory_bytes: 7388
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

s = input()
n = len(s)
def func(s):
    if s == "A" or s == "C" or s == "G" or s == "T":
        return True
    else:
        return False

ans = 0
for i in range(n):
    le = 0
    if func(s[i]):
        le = 1
        for j in range(i+1,n):
            if func(s[j]):
                le += 1
            else:
                break
    ans = max(ans, le)
print(ans)





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

using namespace std;

#define REP(a, b, c) for (register int a = b, _n = c; a <= _n; ++a)
#define DREP(a, b, c) for (register int a = b, _n = c; a >= _n; --a)
#define FOR(a, b, c) for (register int a = b, _n = c; a < _n; ++a)
#define DFOR(a, b, c) for (register int a = b, _n = c; a > _n; --a)
#define EREP(a, b) for (register int a = head[b]; a; a = edge[a].nxt)

inline int rd () {
	int x = 0; char IO = getchar();
	bool f = 0;
	while ((IO < '0' || IO > '9') && IO != '-') IO = getchar();
	if (IO == '-') f = 1, IO = getchar();
	while (IO >= '0' && IO <= '9') x = (x << 3) + (x << 1) + (IO ^ 48), IO = getchar();
	return f ? -x : x;
}

string a, b;

int main () {
   cin >> a >> b;

   int ans = 0;
   FOR (i, 0, 3) if (a[i] == b[i])
      ++ans;

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


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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define FOR(i,m,n) for(int i=(m) ; i<(n) ; i++)
#define FORR(i,m,n) for(int i=(m) ; i>=(n) ; i--)

#define All(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int n;
   cin >> n;
   vector<int> h(n);
   rep(i,n)cin >> h[i];
   int ans = 1;
   for(int i=1;i<n;i++){
      bool flag = true;
      for(int j=0;j<i;j++){
         if(h[j]>h[i]){
            flag = false;
            break;
         }
      }
      if(flag){
         ans++;
      }
   } 
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int a[N],n,c[N];

int main(){
	scanf("%d",&n);
	int ans = n;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		c[x]++;
	}
	int cnt1 = 0, cnt2 = 0;
	for(int i = 1;i<=100000;i++)if(c[i]){
		if(c[i]&1){
			ans -= c[i]-1;
			c[i] = 1;
			cnt1++;
		} else{
			ans -= c[i]-2;
			c[i] = 2;
			cnt2++;
		}
	}
	if(cnt2&1){
		ans -= cnt2+1;
	} else ans -= cnt2;
	printf("%d\n",ans);
	return 0;
}

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

int main() {
	int a,b,c,d,e,k;
	cin >> a >> b >> c >> d >> e >> k;

	if ((e - a) > k){
		cout << ":(" << endl;
	}else{
		cout << "Yay!" << endl;
	}

return 0;
}


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

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

    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        int x = i;
        while(x % 2 == 0) {
            cnt++;
            x /= 2;                
        }
        d.at(i) = cnt;
    }

    int max = 1;
    for (int i = 1; i <= n - 1; i++) {
        if (d.at(max) < d.at(i + 1)) {
            max = i + 1;
        }
    }

    cout << max << endl;
}

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

//20:45開始

int main()
{
	stringstream ss;
    // 入力
    int N,K;
    cin>>N>>K;
    int x[N],y[N];
    for(int i=0;i<N;i++){
    	cin>>x[i]>>y[i];
    }

    //長方形は外側の4つの点で決まる。4つの点の1組または2組が同じ点であることはありうる。
    //全探索してみる。
    int x_temp[4],y_temp[4];
    long long area_min=-1;
    int num_pt=0;
    for(int i1=0;i1<N;i1++){
        x_temp[0]=x[i1];
        y_temp[0]=y[i1];
        for(int i2=i1;i2<N;i2++){
            x_temp[1]=x[i2];
            y_temp[1]=y[i2];

            for(int i3=i2;i3<N;i3++){
                x_temp[2]=x[i3];
                y_temp[2]=y[i3];
                for(int i4=i3;i4<N;i4++){
                    x_temp[3]=x[i4];
                    y_temp[3]=y[i4];

                    long long x_min=x_temp[0];
                    long long x_max=x_temp[0];
                    long long y_min=y_temp[0];
                    long long y_max=y_temp[0];
                    for(int i=0;i<4;i++){
                        if(x_min>x_temp[i])x_min=x_temp[i];
                        if(x_max<x_temp[i])x_max=x_temp[i];
                        if(y_min>y_temp[i])y_min=y_temp[i];
                        if(y_max<y_temp[i])y_max=y_temp[i];
                    }
                    long long area=(x_max - x_min) * (y_max - y_min);
                    num_pt=0;
                    //個数を数える
                    for(int i=0;i<N;i++){
                        if(x[i]>=x_min && x[i]<=x_max && y[i]>=y_min && y[i]<=y_max) num_pt++;
                        if(num_pt>K) break;
                    }
                    if(num_pt==K){
                        if(area_min==-1 || area_min>area) area_min=area;
                    }
                    // cout<<"x:"<<x_min<<"-"<<x_max<<endl;
                    // cout<<"y:"<<y_min<<"-"<<y_max<<endl;
                    // cout<<"area:"<<area<<endl;
                    // cout<<"num_pt:"<<num_pt<<endl<<endl;
                }
            }
        }
    }
    cout<<area_min<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <unordered_map>
#define ll long long
using namespace std;
int a[110],b[110];
int main() {
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    sort(a,a+n);
    sort(b,b+m);
    if(max(a[n-1]+1,x+1)<=min(b[0],y))
        cout<<"No War";
    else
        cout<<"War";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF int(1e9+1)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (1<<18)
ll p[MX],m[MX],N,X,B[MX],L[MX],U[MX],H[MX];
bool cp(ll a,ll b){return -m[a]-p[a]<-m[b]-p[b];}
ll pc(ll u,ll K){
    if(K>=B[u])return (K-B[u])*U[u];
    return (K-B[u])*L[u];
}
bool ok(ll t){
    ll v=t/X,S=0,r=t%X;
    F(N)if(i<v)S+=p[H[i]];
        else S-=m[H[i]];
    if(S>=0)return 1;
    F(N){
        int I=H[i];
        if(i<v&&S-pc(I,X)+pc(I,r)+pc(H[v],X)-pc(H[v],0)>=0)return 1;
        if(i>=v&&S-pc(I,0)+pc(I,r)>=0)return 1;
    }
    return 0;
}
ll bs(ll B=0,ll E=INF){
    ll M;
    while(B<E)
        if(ok(M=(B+E)>>1))E=M;
        else B=M+1;
    return B;
}
int main(void){
    scanf("%lld%lld",&N,&X);
    F(N)scanf("%lld%lld%lld",B+i,L+i,U+i);
    F(N)p[i]=(X-B[i])*U[i],m[i]=B[i]*L[i];
    iota(H,H+N,0),sort(H,H+N,cp);
    printf("%lld\n",bs(0,1e18+666));
    return 0;
}


Measured memory_bytes: 11264
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    if a[i]%2 == 1:
        continue
    else:
        if a[i]%3 != 0 and a[i]%5 != 0:
            print('DENIED')
            exit(0)
print('APPROVED')


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,j,k,inc) for(int i=j ; i<k ; i+=inc)
#define rep(i,n) FOR(i,0,n,1)
#define rfor(i,k,j,dec) for(int i=k-1 ; i>=j ; i-=dec)
#define repr(i,n) rfor(i,n,0,1)

int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif

	int n,m;
	cin >>n>>m;
	for(int x=0 ; x<=n ; x++)
	{
		for(int y=0 ; y<=n ; y++)
		{
			if(2*x+4*y==m and x+y==n){cout <<"Yes";return 0;}
		}
	}
	cout << "No";
	return 0;


}

Measured memory_bytes: 3652
/*
        @uthor: Kashish Gilhotra
        user: CodeChef, CodeForces, HackerEarth, HackerRank, SPOJ: kashish001
*/

#include <bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
  
#define int long long int 
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

double EPS = 1e-9; 
int INF = 1000000005; 
long long INFF = 1000000000000000005LL;
const int mod = 1e9 + 7; 

//#define CI cpp_int
string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << to_string(H) << " " ;
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define RESET(a, b) memset(a, b, sizeof(a)) 
#define EB emplace_back
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define size(v) (int)v.size() 
#define endl "\n"
#define UMO unordered_map
#define USO unordered_set
#define setBits(n) __builtin_popcountll(n)
#define MX *max_element
#define MN *min_element
#define TC int t; cin >> t; while (t--) 

void Panda() {
	char c;
	string s = "";
    for(int i = 0 ; i < 3; i++) {
    	for(int j = 0 ; j < 3; j++) {
    		cin >> c;
    		if(i == j) s += c;
    	}
    }
    cout << s << endl;
}
  
int32_t main() {
 
    FAST;

    
    Panda();

    return 0; 
} 

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

int main(){
  int N;
  cin >> N;
  int num=0;
  for(int i=0; i<=N/4; i++){
    for(int j=0; j<=N/7; j++){
      if(4*i+7*j==N) num++;
    }
  }
  if(num!=0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 100000001;

//int d[202][8];
int n, k;
int x[51], y[51];
const ll ma = 1000000000;
struct item {
	int s, t, c;
};
bool cmp(const item &left,const item &right){
	return left.s < right.s;
}
bool cmp2(const item &left, const item &right) {
	if (left.c == right.c) return left.s < right.s;
	return left.c < right.c;
}
pii chan[31];
bool cmp3(const pii &left, const pii &right) {
	return left.second < right.second;
}
void Recording() {
	int n, c;
	cin >> n >> c;
	item v[100010];
	for (size_t i = 0; i < n; i++)
	{
		cin >> v[i].s >> v[i].t >> v[i].c;
	}

	sort(v, v + n, cmp2);
	int mc = 0;
	for (size_t i = 0; i < n - 1; i++)
	{
		if (v[i].c == v[i + 1].c && v[i].t == v[i + 1].s) {
			v[i + 1].s = v[i].s;
			v[i].s = 1000000;
			//v[i + 1].t = 1000000;
			mc++;
		}
	}

	sort(v, v + n, cmp);
	n -= mc;

	int res = 0;
	int to = 0;
	int count = 1;
	for (size_t i = 0; i < n; i++)
	{
		int st = v[i].s;
		int to = v[i].t;
		for (int j = 0; j < 30; j++)
		{
			if (chan[j].first > to 
				|| st > chan[j].second) {
				chan[j].first = st;
				chan[j].second = to;
				res = max(res, j + 1);
				break;
			}
		}
		sort(chan, chan + res, cmp3);
	}
	cout << res << endl;
}

int main() {
	Recording();
	return 0;
}



Measured memory_bytes: 1408
#include <iostream>
#define INF 1000000
using namespace std;

int n;
int matrix[110][2];
int _dp[110][110];

int dp(int begin,int end){
	if(_dp[begin][end]) return _dp[begin][end];
	if(begin + 1 == end){
		_dp[begin][end] == 0;
		return 0;
	}
	if(begin + 2 == end){
		int temp = matrix[begin][0] * matrix[begin][1] * matrix[end-1][1];
		_dp[begin][end] = temp;
		return temp;
	}
	int min = INF;
	for(int i = begin+1; i<end; i++){
		int temp = dp(begin, i) + dp(i, end)
			+ matrix[begin][0] * matrix[i][0] * matrix[end-1][1];
		if(temp < min) min = temp;
	}
	_dp[begin][end] = min;
	return min;
}

int main(void){
	int n;
	cin >> n;
	
	for(int i=0; i<n; i++) cin >> matrix[i][0] >> matrix[i][1];
	
	cout << dp(0,n) << endl;
	
	return 0;
}


Measured memory_bytes: 3132
class BIT
    def initialize(n)
        @n = n+1
        @dat = Array.new(@n+1, 0)
    end

    def sum(i)
        s = 0
        while i >= 0 do
            s += @dat[i]
            i = (i & (i + 1)) - 1
        end
        s
    end

    def add(i, x)
        while i <= @n do
            @dat[i] += x
            i |= i + 1
        end
    end
end

S = gets.chomp
L = S.length
total = Hash.new(0)
L.times do |i|
    total[S[i]] += 1
end
if total.values.count{|v|v%2==1} > 1
    puts -1
    exit
end
center = total.keys.find{|k|total[k]%2==1}

now = Hash.new(0)
left = ''
L.times do |i|
    if now[S[i]] < total[S[i]]/2
        left << S[i]
    end
    now[S[i]] += 1
end

lpos = {}
rpos = {}
left.length.times do |i|
    lpos[left[i]] ||= []
    rpos[left[i]] ||= []
    lpos[left[i]].push(i)
    rpos[left[i]].unshift(L-1-i)
end
if center
    lpos[center] ||= []
    lpos[center].push(L/2)
end

order = []
L.times do |i|
    if lpos[S[i]].length > 0
        order[i] = lpos[S[i]].shift
    else
        order[i] = rpos[S[i]].shift
    end
end

ans = 0
bit = BIT.new(order.length)
order.length.times do |i|
    ans += i - bit.sum(order[i])
    bit.add(order[i], 1)
end
puts ans

Measured memory_bytes: 7884
#include <stdio.h>

int n;
int a[50],b[50];
int c=0;
void p(int i){printf(c++?" %d":"%d",b[i]);}

void f(int l,int r){
	if(l==r)return;
	if(l+1==r){
		p(l);
		return;
	}
	//bの[l,r)に存在するもののうち、aの中で最も前にあるものを探す
	int idx=-1;
	for(int i=0;i<n;i++){
		for(int j=l;j<r;j++)if(b[j]==a[i])idx=j;
		if(idx!=-1)break;
	}
	f(l,idx);
	f(idx+1,r);
	p(idx);
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n;i++)scanf("%d",b+i);
	f(0,n);
	puts("");
}


Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<math.h>
using namespace std;
  

int main(){
    int N, K;
    cin >> N >> K;
    int d[110];
    vector<vector<int>> A(110, vector<int>(110));
    
    for(int i=0; i<K; i++){
        cin >> d[i];
        for(int j=0; j<d[i]; j++){
            cin >> A.at(i).at(j);
        }
    }
    
    vector<int> frag(110, 0);
    
    for(int i=0; i<K; i++){
        for(int j=0; j<d[i]; j++){
            frag[A.at(i).at(j)]++;
            //cout << "i=" << i << "  j=" << j << "   A(i,j)=" << A.at(i).at(j) << "   frag[A.at(i).at(j)]=" << frag[A.at(i).at(j)] << endl;
        }
    }
    
    int count=0;
    
    for(int i=1; i<=N; i++){
        //cout << "i=" << i << "   frag[i]=" << frag[i] <<endl;
        if(frag[i]==0){
            count++;
        }
    }
    
    cout << count << endl;;
    
    
    
    return 0;
}


Measured memory_bytes: 3684
#include <stdio.h>
int main(void){
	int a,b,c,d,sum=0;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	sum+=(a<b?a:b);
	sum+=(c<d?c:d);
	printf("%d",sum);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define             MOD                     100000007
using namespace std;


int main() {

    int n,r;

    cin>>n>>r;

    if(n>=10){
        cout<<r<<endl;
    }else{
        cout<<r+(100*abs(10-n))<<endl;
    }

    return 0;
}


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

using namespace std;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a;
  cin >> a;
  if (a == 0) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> v;
  while (a != 0) {
    v.push_back(a % -2);
    a /= -2;
    if (v.back() < 0) {
      v.back() += 2;
      a += 1;
    }
  }
  reverse(v.begin(), v.end());
  for (int i = 0; i < (int) v.size(); ++i) {
    cout << v[i];
  }
  cout << '\n';
  return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll cnt0 = 0;
    ll cnt1 = 0;
    ll cnt2 = 0;
    rep(i, N) {
        ll c = 0;
        ll a = A[i];
        while (a % 2 == 0) {
            a /= 2;
            c++;
        }
        if (c == 0) {
            cnt0++;
        } else if (c == 1) {
            cnt1++;
        } else {
            cnt2++;
        }
    }
    if (cnt1 > 0) {
        cnt0++;
        N -= cnt1 - 1;
    }
    if (N % 2 == 0) {
        if (cnt2 >= cnt0) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    } else {
        if (cnt2 + 1 >= cnt0) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 1024
#!/usr/bin/env python3

from sys import stdin


def main():
    n, k = map(int, stdin.readline().split())
    d = []
    A = []
    for i in range(k):
        d.append(int(stdin.readline()))
        A.append(list(map(int, stdin.readline().split())))

    okashi = [False] * n
    for a in A:
        for j in a:
            okashi[j - 1] = True
    print(okashi.count(False))
    pass


if __name__ == "__main__":
    main()


Measured memory_bytes: 9152
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<deque>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> nums;
    int now=1;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(s[i]==(char)('0'+now)){
            cnt++;
        }else{
            nums.push_back(cnt);
            now = 1-now;
            cnt = 1;
        }
    }
    if(cnt!=0) nums.push_back(cnt);
    if(nums.size()%2==0) nums.push_back(0);

    int cum[nums.size()+1];
    cum[0] = 0;
    for(int i=0;i<nums.size();i++){
        cum[i+1] = cum[i] + nums[i];
    }

    int ans = 0;
    int add = 2*k+1;
    for(int i=0;i<nums.size();i+=2){
        int left = i;
        int right = min(i+add,(int)nums.size());
        int sum = cum[right]-cum[left];
        ans = max(ans,sum);
    }

    cout << ans << endl;


}

Measured memory_bytes: 1272
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D: Recording
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_T = 100000;
const int MAX_C = 30;
const int INF = 1 << 30;

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

/* global variables */

vpii cps[MAX_C];
int dp[MAX_T + 5];

/* subroutines */

/* main */

int main() {
  int n, c;
  scanf("%d%d", &n, &c);

  int maxt = 0;
  for (int i = 0; i < n; i++) {
    int si, ti, ci;
    scanf("%d%d%d", &si, &ti, &ci);
    ci--;
    cps[ci].push_back(pii(si, ti));
    if (maxt < ti) maxt = ti;
  }

  for (int i = 0; i < c; i++) {
    vpii &cpi = cps[i];
    sort(cpi.begin(), cpi.end());
    int prvt = -1;
    for (int j = 0; j < cpi.size(); j++) {
      int &sj = cpi[j].first, &tj = cpi[j].second;
      if (prvt < sj) sj--;
      dp[sj]++, dp[tj]--;
      prvt = tj;
    }
  }

  int maxd = 0;
  for (int t = 0; t <= maxt; t++) {
    if (maxd < dp[t]) maxd = dp[t];
    dp[t + 1] += dp[t];
  }

  printf("%d\n", maxd);
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 15;
int ans=0,n;
vector<pii> g[N];
bool check(int s){
    for(int i=0;i<n;++i){
        if(s&(1<<i)){
            for(auto p:g[i]){
                if(((s>>p.first)&1)!=p.second)
                    return false;
            }
        }
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=0,x,y,m;i<n;++i){
        scanf("%d",&m);
        while(m--){
            scanf("%d %d",&x,&y); x--;
            g[i].push_back(make_pair(x,y));
        }
    }
    for(int i=0;i<(1<<n);++i){
        if(check(i)){
            //printf("%d\n",i);
            ans=max(ans,__builtin_popcount(i));
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 256
#include<stdio.h>
long long MIN(long long a,long long b){return a<b?a:b;}
int main(){
  long long n,d[500][500],i,j,k,min,s=0;
  scanf("%lld",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++)scanf("%lld",&d[i][j]);
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(i==j)continue;
      min=1e18;
      for(k=0;k<n;k++){
	if(i==k||j==k)continue;
	min=MIN(min,d[i][k]+d[k][j]);
      }
      if(min<d[i][j])goto END;
      if(min>d[i][j])s+=d[i][j];
      //printf("%lld %lld %lld\n",i,j,s);
    }
  }
  printf("%lld\n",s/2);
  return 0;
 END:;
  printf("-1\n");
  return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

const int mod = 1000000007;
map<pair<string, int>, int> dp;

bool good(string t)
{
    if (t.find("AGC") != string::npos)
        return false;

    FOR(i, 0, 3) {
        swap(t[i], t[i + 1]);
        if (t.find("AGC") != string::npos)
            return false;
        swap(t[i], t[i + 1]);
    }

    return true;
}

int f(int n, string tail)
{
    if (!good(tail))
        return 0;

    if (n == 0)
        return 1;

    auto key = PAIR(tail, n);
    if (dp.find(key) != dp.end())
        return dp[key];


    int ret = 0;
    string s = "ACGT";
    for (char c : s)
        {
            string newtail = tail.substr(1) + c;
            ret += f(n - 1, newtail);
            if (ret >= mod)
                ret -= mod;
        }

    return dp[key] = ret;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    cin >> N;
    int ret = 0;
    if (N == 3)
        ret = 61;
    else {
        string s = "ACGT";
        for (char a : s)
            for (char b : s)
                for (char c : s)
                    for (char d : s) {
                        string t = "ABCD";
                        t[0] = a;t[1] = b;t[2] = c;t[3] = d;
                        ret = (ret + f(N - 4, t)) % mod;
                    }
    }

    cout << ret << endl;
    return 0;
};


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
	cin>>s;
	if(s=="SUN")
	printf("7");
	if(s=="MON")
	printf("6");
	if(s=="TUE")
	printf("5");
	if(s=="WED")
	printf("4");
	if(s=="THU")
	printf("3");
	if(s=="FRI")
	printf("2");
	if(s=="SAT")
	printf("1");
	return 0;
}

Measured memory_bytes: 256
import java.math.*

fun main(args: Array<String>) {
    val (n, k) = readInputLine().split(" ").map{it.toLong()}
    val aList = readInputLine().split(" ").map{it.toLong()}

    // dp[i][j] 上位i桁目を見たとき、j = 1ならばKと同一ビット列、j = 0ならばKと異なるビット列(Kより小さい)のときの総和
    val dp = Array(50, {Array(2, {-1L})})
    
    dp[0][1] = 0L
    
    for (i in 1..49) {
        val mask = 1L shl (50 - i - 1)
        
        var cnt1 = 0
        
        for (a in aList) {
            if (a and mask != 0L) {
                cnt1++
            }
        }
        
        val cnt0 = n - cnt1
        
        // i - 1桁目がちょうど一致する場合からの遷移
        if (mask and k != 0L) {
            // Kの上位からiビット目が1
            if (dp[i - 1][1] != -1L) {
                // *一致しない*ビットの数が総和に寄与するので、ビットと反対のビットのカウントを用いる
                dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + mask * cnt0)
                dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + mask * cnt1)
            }
        } else {
            // Kの上位からiビット目が0
            if (dp[i - 1][1] != -1L) {
                // iビット目が0なので、iビット目を1とする遷移はできない
                dp[i][1] = Math.max(dp[i][0], dp[i - 1][1] + mask * cnt1)
            }
            
        }
        
        // i - 1桁目がちょうど一致しない場合の遷移はKのビットに依存しない
        if (dp[i - 1][0] != -1L) {
            dp[i][0] = Math.max(dp[i][0], Math.max(dp[i - 1][0] + mask * cnt0, dp[i - 1][0] + mask * cnt1)) 
        }
    }

    println(Math.max(dp[49][0], dp[49][1]))
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 73860
/* ****Tciitb**** */
                     
#include<bits/stdc++.h>
#define io          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define ll          int long long
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll ,ll >
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=a-1;i>=b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;
#define N 1000005 



 
int main()
{
  io
  ll n;cin>>n;if(n<=999)cout<<"ABC";else cout<<"ABD";
}
       

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi           first
#define se           second
#define ll           long long
#define pb           push_back
#define mp           make_pair
#define pll          pair<ll,ll>
#define pii          pair<int,int>
#define all(x)       (x).begin(),(x).end()
#define isWorking()  cout<<"Wroking"<<endl
#define FOR(i,x,y)   for(int i=x; i<y; i++)
#define SORT(x)      sort(x.begin(),x.end())
#define PRINT(ok)    cout<<(ok? "YES":"NO")<<endl
#define Fast_Input   ios_base :: sync_with_stdio(false), cin.tie(NULL);
typedef vector < int > VI;
const ll mod= 1e9+7,INF=1e18,mx= 5e6+5,mn=100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    //cin>>testCase;
    while(testCase--){
        int ok=1;
        int n; cin>>n;
        while(n--){
            int k; cin>>k;
            if(k%2==0){
                if(k%3==0 || k%5==0){

                }else ok=0;
            }
        }
    cout<<(ok==1? "APPROVED":"DENIED")<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+5)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Measured memory_bytes: 101592
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    int n,k,q,i,q1;
    cin>>n>>k>>q;
    q1=q;
    int arr[n+1];
    for(i=0;i<=n;i++)
    arr[i]=0;
    while(q--)
    {
        int a;
        cin>>a;
        arr[a]++;
    }
    for(i=1;i<=n;i++)
    {
        arr[i]=k-q1+arr[i];
        if(arr[i]<=0)
        cout<<"No"<<endl;
        else
        cout<<"Yes"<<endl;
    }
}

Measured memory_bytes: 1024
# coding: utf-8

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ansnum = [0] * N
for a in A:
    ansnum[a - 1] += 1
for n in ansnum:
    if (Q - n < K):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 8640
#include<stdio.h>
#include<string.h>
int main(void)
{
	int N;
	double sum = 0.0;
	double x[11];
	char u[11][100];
	scanf("%d", &N);
	char J[100] = { 'J','P','Y' }, B[100] = { 'B','T','C' };
	for (int i = 0; i < N; i++) {
		scanf("%lf", &x[i]); scanf("%s",u[i]);
	}
	for(int i=0;i<N;i++){
		if (strcmp(u[i],J)==0) {
			sum += x[i];
			//printf("sum=%f ", sum);
		}
		else if (strcmp(u[i], B) == 0) {
			sum += x[i] * 380000.0;
			//printf("sum=%f ", sum);
		}
	}
	printf("%f ", sum);
	return 0;
}

Measured memory_bytes: 128
n = int(input())
a = [int(i) for i in input().split()]

li = [0]*(n+1)

for i in range(n):
    li[i+1] = li[i] + a[i]
    
#print(li)

li_sum = sum(a)

ans = 10**18

for i in range(n):
    #print(ans)
    if ans > abs(li_sum - 2*li[i]):
        ans = abs(li_sum - 2*li[i])
        
print(ans)

Measured memory_bytes: 26060
w,h,n=map(int,input().split())
a=[[int(i)for i in input().split()]for j in range(n)]
S=[[0,w],[0,h]]
for i in a:
    if i[2]==1:
        S[0][0]=max(i[0],S[0][0])

    if i[2]==2:
        S[0][1]=min(i[0],S[0][1])

    if i[2]==3:
        S[1][0]=max(i[1],S[1][0])

    if i[2]==4:
        S[1][1]=min(i[1],S[1][1])

ans=max(0,(S[0][1]-S[0][0]))*max(0,(S[1][1]-S[1][0]))
print(ans)

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

l = []

for i in range(n):
    l.append(list(map(int, input().split())))
l.sort(key=lambda x:x[0])
# print(l)

cnt = 0
money = 0
while cnt < m:
    for temp in l:
        if cnt > m:
            break
        for _ in range(temp[1]):
            cnt = cnt + 1
            if cnt <= m:
                money = money + temp[0]
            else:
                break

print(money)



Measured memory_bytes: 29024
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] cnt = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            cnt[(int) (s.charAt(i) - 'a')]++;
        }
        for (int i : cnt) {
            if (i % 2 != 0) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

Measured memory_bytes: 23380
#include <stdio.h>
#include <math.h>
  
typedef struct{
  double x;
  double y;
} Point;
  
void koch(int n,Point a,Point b){
  double rad;
  Point s,t,u;
  if (n == 0) return ;
  rad = M_PI*60.0/180.0;
  
  s.x = (2.0*a.x + 1.0*b.x)/3.0;
  s.y = (2.0*a.y + 1.0*b.y)/3,0;
  t.x = (1.0*a.x + 2.0*b.x)/3.0;
  t.y = (1.0*a.y + 2.0*b.y)/3.0;
  u.x = (t.x - s.x)*cos(rad) - (t.y - s.y)*sin(rad) + s.x;
  u.y = (t.x - s.x)*sin(rad) + (t.y - s.y)*cos(rad) + s.y;
  
  koch(n-1,a,s);
  printf("%.8f %.8f\n",s.x,s.y);
  koch(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  koch(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  koch(n-1,t,b);
}
  
int main(){
  Point a,b;
  int n;
  scanf("%d",&n);
  
  a.x = 0.0;
  a.y = 0.0;
  b.x = 100.0;
  b.y = 0.0;
  
  printf("%.8f %.8f\n",a.x,a.y);
  koch(n,a,b);
  printf("%.8f %.8f\n",b.x,b.y);
  return 0;
}



Measured memory_bytes: 2112
#include <stdio.h>

int main( void )
{
  	int a;
  	char s[10];
  
  	scanf( "%d", &a );
  	scanf( "%s", s );
  
  	if( a >= 3200 ) {
		printf( "%s\n" , s );
    }
  	else {
     	printf( "red\n" );
    }
  
 	return 0; 
}

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

int main( void )
{
    int a, b;
    cin >> a >> b;
    if ( a % 3 == 0 || b % 3 == 0 || ( a + b ) % 3 == 0 )
    {
        cout << "Possible" << endl;
    }
    else
    {
        cout << "Impossible" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e9 + 7;
const int MAX_N = 2e5, MAX_M = 1e5, MAX_K = 1e9;

//qsortでの比較用の関数 cmp
//qsort(配列名,要素数,sizeof(要素型),cmp)
int cmp(const void *p, const void *q) {
	return *(int*)p - *(int*)q;
}

int n;
int a[MAX_N];

int solve() {
	int par = 1;
	rep(i, n) {
		if (a[i] == par) {
			par += 1;
		}
	}
	return par;
}	
int main() {
	cin >> n;
	rep(i, n) cin >> a[i];
	if (solve() <= 1) cout << -1 << endl;
	else cout << n - solve() + 1 << endl;
}


Measured memory_bytes: 1024
import itertools

n,m = [int(x) for x in input().split()]
li = []
for _ in range(m):
    li.append({int(x) for x in input().split()})

a = itertools.permutations(range(2,n+1))
count = 0
for i in a:
    x = [1] + list(i)
    for i in range(n-1):
        if not {x[i],x[i+1]} in li:
            break
    else:
        count += 1
print(count)


Measured memory_bytes: 41180
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll a, b;
  cin >> a >> b;
  if (a == b) cout << "Draw" << endl;
  else if (a == 1) cout << "Alice" << endl;
  else if (b == 1) cout << "Bob" << endl;
  else if (a > b) cout << "Alice" << endl;
  else if (a < b) cout << "Bob" << endl;

  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;
static const ll MOD = 1000000007;// 1e9 + 7

int main() {
	ll N, K; cin >> N >> K;
	ll V[50];

	rep(i, 0, N) cin >> V[i];
	ll M = min(N, K);

	ll maxV = 0;
	repe(l, 0, M) {
		repe(r, 0, M) {
			if ((l + r) <= M) {
				vector<ll> v;
				ll total = 0;
				rep(i, 0, l) {
					ll x = V[i];
					v.push_back(V[i]);
					total += x;
				}

				rep(i, 0, r) {
					ll x = V[N - i - 1];
					v.push_back(x);
					total += x;
				}

				sort(v.begin(), v.end());
				ll k = K - (l + r);

				for (vector<ll>::iterator it = v.begin(); it != v.end(); it++) {
					if (k-- > 0 && *it < 0) total -= *it;
				}

				maxV = max(total, maxV);
			}
		}
	}

	cout << maxV << endl;

	return 0;
}

Measured memory_bytes: 256
X=int(input())
K=int(input())
r=list(map(int,input().split()))
Q=int(input())
p=[tuple(map(int,input().split())) for i in range(Q)]

N=Q
L=0
R=Q-1
start=0
sign="-"

# N: 処理する区間の長さ

N0 = 2**(N-1).bit_length()
data = [0]*(2*N0)
INF = 0
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] += v

        if L & 1:
            data[L-1] += v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def query(k):
    k += N0-1
    s = INF
    while k >= 0:
        s += data[k]
        k = (k - 1) // 2
    return s

q=[]
for i in range(Q):
    t,a=p[i]
    p[i]=(a,t,i)

p.sort()
dic=[-1]*Q
for i in range(Q):
    a,t,id=p[i]
    update(i,i+1,a)
    dic[id]=i
    q.append((t,id,0))

for i in range(K):
    q.append((r[i],-1,r[i]-r[i-1]*(i>0)))

q.sort()
ans=[0]*Q
for val,id,c in q:
    if id==-1:
        if sign=="-":
            update(L,R+1,-c)
            while query(L+1)<0 and L<R:
                L+=1
            a=query(L)
            if a<0:
                update(L,L+1,-a)
            start=val
            sign="+"
        else:
            update(L,R+1,c)
            while query(R-1)>X and L<R:
                R-=1
            a=query(R)
            if a>X:
                update(R,R+1,X-a)
            start=val
            sign="-"
    else:
        pid,id=id,dic[id]
        if sign=="-":
            if id<L:
                res=max(query(L)-(val-start),0)
            elif id>R:
                res=max(query(R)-(val-start),0)
            else:
                res=max(query(id)-(val-start),0)
        else:
            if id<L:
                res=min(query(L)+(val-start),X)
            elif id>R:
                res=min(query(R)+(val-start),X)
            else:
                res=min(query(id)+(val-start),X)
        ans[pid]=res


for i in range(Q):
    print(ans[i])


Measured memory_bytes: 144656
#include <iostream>
#include <algorithm>
using namespace std;
int sum,v[200003],t[200003],n,a,k,nr;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        ++v[a];
    }
    for(int i=1;i<=n;++i)
    {
        if(v[i])
        {
            t[++nr]=v[i];
        }
    }
    sort(t+1,t+nr+1);
    for(int i=1;i<=nr-k;++i)
    {
        sum+=t[i];
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
    int p,q,r;
    scanf("%d%d%d",&p,&q,&r);
    int a=p+q;
    int b=p+r;
    int c=q+r;
    if(a<=b)
    {
        if(a<=c)
        {
            printf("%d\n",a);
        }
        else
        printf("%d\n",c);

    }
    else
    {
        if(c>=b)
        {
            printf("%d\n",b);
        }
        else
            printf("%d\n",c);
    }


    return 0;

}




Measured memory_bytes: 128