akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<array>
#include<functional>
#include<iomanip>
#include<ios>
using namespace std;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)

typedef int value_type; /* ソートするキーの型 */

value_type med3(value_type x, value_type y, value_type z)
/* x, y, z の中間値を返す */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}

void quicksort(value_type a[], int left, int right,value_type index[])
/* クイックソート
 * a     : ソートする配列 
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 * index: index配列
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            tmp = index[i]; index[i] = index[j]; index[j] = tmp;
            i++; j--;
        }
        quicksort(a, left, i - 1,index);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right,index); /* 分割した右を再帰的にソート */
    }
}

bool is753(int n){
    bool x[3]={false,false,false};

    while(n>0){
        switch (n%10){
            case 3:
                x[0]=true;
                break;
            case 5:
                x[1]=true;
                break;
            case 7:
                x[2]=true;
                break;
            default:
            return false;
        }
        n/=10;
    }
    if(x[0]&& x[1]&&x[2]){
        return true;
    }else{
        return false;
    }

}

int dfs(int n,int N){
    if (n>N){
        return 0;
    }
    

    int ret;
    if(is753(n)){
        ret=1;
    }else{
        ret=0;
    }
    FOR(i,3){
        ret+=dfs(10*n + (2*i+3),N);
    }
    return ret;
}


int main(){
    int N,K;

    cin >> N >>K;

    long ans;

    if(K%2==1){
        ans=pow(N/K,3);
    }else{
        ans=pow(N/K,3)+pow((N+(K/2))/K ,3);
    }



    cout <<ans<<endl;

    return 0;

    


}

Measured memory_bytes: 384
//Volume0-0089
import java.util.Scanner;

public class Main {

    //declare
	private static final int     WIDTH  = 50,
			                     HEIGHT = 99;
	private static       int     l;
    private static       int[][] route  = new int[HEIGHT][WIDTH],
    		                     table,
   		                         cost;

	public static void main(String[] args){

        String[] s;

        //input
        Scanner sc = new Scanner(System.in);

        int i;
        for(i=0;sc.hasNext();i++){
        	s = sc.nextLine().split(",");
        	for(int j=0;j<s.length;j++){
        		route[i][j] = Integer.parseInt(s[j]);
        	}
        }
        chg_tbl(i);

        //calculate,output
        System.out.println(dp());
	}

	private static void chg_tbl(int line_cnt){

		l = line_cnt/2+1;
		table = new int[l][l];

		for(int i=0;i<l;i++){
			for(int j=0;j<l-i;j++){
				table[i][j] = route[i+j][j];
			}
		}

		for(int i=1;i<l;i++){
			for(int j=l-i;j<l;j++){
				table[i][j] = route[i+j][l-i-1];
			}
		}
	}

	private static int dp(){

		int L = l+1;
		cost = new int[L][L];

		for(int i=1;i<L;i++){
			for(int j=1;j<L;j++){
				if( cost[i-1][j] > cost[i][j-1]){
					cost[i][j] = cost[i-1][j] + table[i-1][j-1];
				} else {
					cost[i][j] = cost[i][j-1] + table[i-1][j-1];
				}
			}
		}
		return cost[l][l];
	}
}

Measured memory_bytes: 21088
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int a,b;
  cin>>a>>b;
  if(a==1)
  {
   if(b==2) cout<<"3";
   else cout<<"2";
   }
  else if(a==2)
  {
   if(b==1) cout<<"3";
   else cout<<"1";
   }
   else
   {
    if(b==1) cout<<"2";
    else cout<<"1";
    }
  }

Measured memory_bytes: 3564
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        String[] s=new String[n];
        int[] t=new int[n];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
            t[i]=sc.nextInt();
        }
        String sleep=sc.next();
        boolean flag=false;
        int ans=0;
        for(int i=0;i<n;i++){
            if(flag)ans+=t[i];
            if(sleep.equals(s[i]))flag=true;
        }
        System.out.println(ans);
 
    }


}

Measured memory_bytes: 23892
#include <stdio.h>
using namespace std;

int n,a[200001],x;

int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    x^=a[i];
  }
  for(int i=0;i<n;i++){
    printf("%d ",x^a[i]);
  }
  return 0;
}


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    ll a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < min(k, (ll)42); i++){
        ll d[n] = {0};
        for(int j = 0; j < n; j++){
            ll lb = max((ll)0, j - a[j]);
            ll ub = min(n, j + a[j]);
            d[lb]++;
            if(ub + 1 < n)
                d[ub + 1]--;
        }
        a[0] = d[0];
        for(int j = 1; j < n; j++){
            a[j] = d[j] + a[j - 1];
        }
    }
    for(int i = 0 ; i < n; i++){
        cout << a[i] << ' ';
    }
    return 0;
}

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

int main(){
	  while(1){
			int H; cin >> H;
			if(!H) break;
			int b[H][6]={};

			for(int i=0; i<H; i++)
				  for(int j=0; j<5; j++)
						cin >> b[i][j];

			bool f=true;
			int ans = 0;
			while(f){
				  f=false;
				  // ?°´??? 
				  for(int i=0; i<H; i++){
						int pre = 0;
						int len = 1;
						for(int j=1; j<6; j++){
							  if(b[i][pre] == b[i][j]){
									len++;
							  }
							  else{
									if(len >= 3 and b[i][pre] != -1){
										  ans += b[i][pre]*len;
										  //cout << b[i][pre] << "*" << len << endl;
										  int tmp = b[i][pre];
										  for(int k=j-1; b[i][k] == tmp; k--)
												b[i][k] = -1;
										  f = true;
									}
									pre = j;
									len = 1;
							  }
						}
				  }

				  // ??????
				  for(int i=H-1; i>=0; i--){
						for(int j=0; j<5; j++){
							  if(b[i][j] == -1)
									for(int k=i-1; k>=0; k--)
										  if(b[k][j] != -1){
												swap(b[k][j],b[i][j]);
												break;
										  }
							  
						}
				  }


			}
			cout << ans << endl;
	

	  }
}

Measured memory_bytes: 3076
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N , M; cin >> N >> M;
  vector<ll> c(N);
  rep(i,M) cin >> c[i];

  vector<vector<ll> > dp(2, vector<ll>(N + 1, INF));
  // dp[i][j]はi種類でj円払えるための最小必要枚数
  dp[0][0] = 0;
  ll cnt = 0;
  rep(i,M){
    cnt++;
    rep(j, N + 1){
      if(j < c[i]) dp[1][j] = dp[0][j];
      else{
        dp[1][j] = min(dp[0][j] , dp[1][j - c[i]] + 1);
      }
    }
    rep(j , N + 1){
      dp[0][j] = dp[1][j];
    }
  }
  ll ans = dp[0][N];
  cout << ans << endl;
}



Measured memory_bytes: 4376
#include "bits/stdc++.h"
using namespace std;

int main() 
{
	int a, b;
	cin >> a >> b;
	if (a % 2 == 1 && b % 2 == 1)
	{
		cout << "Odd" << endl;
	}
	else
	{
		cout << "Even" << endl;
	}
}


Measured memory_bytes: 256
N = str(input())
if N[-1] == '2' or N[-1] == '4' or N[-1] == '5' or N[-1] == '7' or N[-1] == '9':
    print('hon')
elif N[-1] == '0' or N[-1] == '1' or N[-1] == '6' or N[-1] == '8':
    print('pon')
elif N[-1] == '3':
    print('bon')

Measured memory_bytes: 9080
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		long lsum[][] = new long[n][n]; // local sum:部分和
		for ( int c = 0; c < n; c++ ) {
			lsum[c][c] = in.nextInt();
			for ( int r = 0; r < c; r++ ) {
				lsum[r][c] = lsum[r][c - 1] + lsum[c][c];
			}
		}

		long cost[][] = new long[n][n]; // 累積コスト
		Long min = Long.MAX_VALUE;
		for ( int r = n - 2; 0 <= r; r-- ) {
			for ( int c = r + 1; c < n; c++ ) {				
				for ( int i = r; i <= c - 1; i++ ) {
					if ( min > cost[r][i] + cost[i + 1][c] ) {
						min = cost[r][i] + cost[i + 1][c];
					}
				}
				cost[r][c] = min + lsum[r][c];
				min = Long.MAX_VALUE;
			}
		}

		System.out.println(cost[0][n - 1]);
		in.close();
	}
}

Measured memory_bytes: 94272
#include <stdio.h>
int main(void)
{
	int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if((x + r <= W && x - r >= 0) && (y + r <= H && y - r >= 0))
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
	
}


Measured memory_bytes: 2688
while True:
	arr = list(map(int, input().split()))
	m = arr[0]
	f = arr[1]
	r = arr[2]
	
	if m == -1 and f == -1 and r == -1:
		break
	
	total = m + f
	if m == -1 or f == -1: print('F')
	elif total >= 80: print('A')
	elif total >= 65: print('B')
	elif total >= 50: print('C')
	elif total >= 30 and r >= 50: print('C')
	elif total >= 30: print('D')
	else: print('F')



Measured memory_bytes: 5596
n, m, q = map(int,input().split())
abcd = []
for _ in range(q):
    abcd.append(list(map(int,input().split())))

a_l = [1] * n
ans = 0
while True:
    ans_tmp = 0
    for a, b, c, d in abcd:
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    if a_l == [m]*n:
        break
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break
    for i in range(1,n):
        while a_l[i-1] > a_l[i]:
            a_l[i] += 1

print(ans)



Measured memory_bytes: 9228
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef LOCAL
    #define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define debug(...) 42
    #define eprintf(...) 42
#endif

#define PI 3.1415926535897932384626433832795
#define INF 2e9
#define SINV(t) greater<t>()
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define FOREACH(i, v) for(auto i=(v).begin(); i!=(v).end(); ++i)
#define ALL(x) (x).begin(),(x).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 (b<a) { a=b; return 1; } return 0; }

typedef long long ll;
#define vv(t) vector<t>

#define CHC(mp, x) if(mp.end() != mp.find(x))

#pragma endregion

template<typename T>
void SV(vector<T> v){
    REP(i,v.size()){
        #ifdef LOCAL
            cout << i << " : " << v[i] << endl;
        #endif
    }
}
int bitCount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16);
}

vv(vv(int)) mp(9);


int N, M;
int f(int num, int now){
    num = num | (1<<now);
    if((num>>1)+1 == 1<<N){
        debug("complete" ,now, num);
        return 1;
    }
    int sum = 0;
    REP(i, mp[now].size()){
        debug(now, i, mp[now][i]);
        if((num>>mp[now][i])&1){
            continue;
        }
        SV(mp[now]);
        sum += f(num, mp[now][i]);
    }
    return sum;
}

int main(void){
    cin >> N >> M;
    int a, b;
    REP(i, M){
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    //SV(mp[1]);
    cout << f(0, 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#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 lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T mpow(T a, T n) {
   T res = 1;
   for(;n;n>>=1) {
      if (n & 1) res = res * a;
      a = a * a;
   }
   return res;
}

//cin.tie(0);ios::sync_with_stdio(false);

vector<vector<int>> v(100010,vector<int>(0));

int dp[100010]={};

int dfs(int now){
    priority_queue<int> q;

    rep(i,0,siz(v[now])){
        if(dp[v[now][i]]==0){
            dp[v[now][i]]=dfs(v[now][i]);
        }
        q.push(dp[v[now][i]]);
    }

    if(siz(v[now])==0)return 0;

    int add=1;
    while(!q.empty()){
        dp[now]=max(dp[now],q.top()+add);
        q.pop();
        add++;
    }

    return dp[now];
}

signed main(){
    int n;cin>>n;
    rep(i,1,n){
        int in;cin>>in;in--;
        v[in].pb(i);
    }

    cout<<dfs(0)<<endl;

}

Measured memory_bytes: 13952
N=int(input())
L=list(map(int,input().split()))

L.sort(reverse=True)

ans=0
l=len(L)
for i in range(l-2):
    for j in range(i+1,l-1):
        for k in range(j+1,l):
            if L[i] < L[j]+L[k] and L[k]!=L[i] and L[j]!=L[k] and L[i]!=L[j] :
                ans+=1
print(ans)

Measured memory_bytes: 9084
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <numeric>
#include <iomanip>

int main(void) {
	int a, b;

	std::cin >> a >> b;

	std::cout << std::fixed << std::setprecision(5) << (1.0 * a) / b << std::endl;

	return 0;
}

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, prev, visited[:])
        
    return res

print(DFS(1, 0, []))

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

int main(){
  int a[5];
  rep(i,5) cin >> a[i];
  int k;
  cin >> k;
  bool yes = true;
  for (int i = 0; i < 5; ++i){
    for (int j = i+1; j < 5; ++j){
      if(a[j]-a[i] > k) yes = false;
    }
  }
  if(yes)puts("Yay!");
  else puts(":(");
  return 0;
}

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

map<ll, ll> prime; //素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n)
{
    if (n <= 1)
        return;
    ll l = sqrt(n);
    for (ll i = 2; i <= l; i++)
    {
        if (n % i == 0)
        {
            prime_factorize(i);
            prime_factorize(ll(n / i));
            return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime[n]++;
    return;
}

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

    ll ans = 0;
    for (auto p : prime)
    {
        ll i = 1;
        ll sum = 0;
        while (1)
        {
            sum += i;
            if (sum > p.second)
                break;
            ans++;
            ;
            i++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
// B - Touitsu

using namespace std;

int cnt[105][30];

int main() {
    int N,i,j,ans,temp;
    string A,B,C;

    cin >> N;
    cin >> A;
    cin >> B;
    cin >> C;

    for (i = 0;i < N;i++) {
        cnt[i][A[i] - 'a']++;
        cnt[i][B[i] - 'a']++;
        cnt[i][C[i] - 'a']++;
    }

    ans = 0;
    for (i = 0;i < N;i++) {
        temp = 0;
        for (j = 0;j < 26;j++)
            temp = max(temp,cnt[i][j]);

        ans += (3 - temp);
    }

    printf("%d\n",ans);

    return 0;
}


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

int main(){
    int i,m,tmp;
    ll n,sum=0;
    scanf("%lld %d",&n,&m);
    for(i=0;i<m;i++) {
        scanf("%d",&tmp);
        sum+=tmp;
    }
    if(sum>n) printf("-1");
    else {n=n-sum;printf("%lld",n);}
}


Measured memory_bytes: 3828
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		// 計算
		int result = 0;
		result = min(n*a, b);

		// 出力
		System.out.println(result);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For(i, 0, n)
#define rrep(i, n) rFor(i, n, 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int main(){
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(k, min(s.size(), t.size()) + 1){
        set<array<int, 26>> S;
        array<int, 26> a;
        fill(a.begin(), a.end(), 0);
        rep(i, k) ++a[s[i] - 'a'];
        rep(i, s.size() - k + 1){
            S.insert(a);
            --a[s[i] - 'a'];
            if(i + k < s.size()) ++a[s[i + k] - 'a'];
        }

        array<int, 26> b;
        fill(b.begin(), b.end(), 0);
        rep(i, k) ++b[t[i] - 'a'];
        rep(i, t.size() - k + 1){
            if(S.find(b) != S.end()){
                chmax(ans, k);
                break;
            }
            --b[t[i] - 'a'];
            if(i + k < t.size()) ++b[t[i + k] - 'a'];
        }
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 3628
#include <cstdio>

int n, k;
int A[101];

bool dp[100001];

int main(){
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; i++) scanf("%d", A+i);
  A[n] = k+1;
  for(int i = 1; i <= k; i++){
    for(int j = 0; !dp[i] && A[j] <= i; j++) dp[i] = !dp[i-A[j]];
  }
  if(dp[k]) puts("First");
  else puts("Second");
  return 0;
}


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

using namespace std;

#define MAX 101

int d[MAX],visited[MAX];
vector<int> G[MAX];
queue<int> Q;

int main(){
  int n; cin >> n;
  for(int i=0;i<n;i++){
    int u,k; cin >> u >> k;
    for(int i=0;i<k;i++){
      int v; cin >> v;
      G[u].push_back(v);
    }
  }
  //bread first search
  for(int i=1;i<=n;i++){
    visited[i]=0;
    d[i]=-1;
  }
  visited[1]=1;
  d[1]=0;
  Q.push(1);
  while(!(Q.empty())){
    int u=Q.front(); Q.pop();
    for(int v=0;v<G[u].size();v++){
      if(visited[G[u][v]]==0){
        visited[G[u][v]]=1;
        d[G[u][v]]=d[u]+1;
        Q.push(G[u][v]);
      }
    }
  }
  for(int i=1;i<=n;i++){
    cout << i << " " << d[i] << endl;
  }
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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

int main () {
  int n, k;
  cin >> n >> k;
  vi x(n);
  rep(i,n) cin >> x[i];
  
  int ans = INF;
  // 0 1 2 ... n-k-2 n-k-1 n-k n-k+1 ... n-1
  rep(i,n-k+1) {
    int near_x = min(abs(x[i]), abs(x[i+k-1]));
    ans = min(ans, near_x + x[i+k-1] - x[i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007


signed main(){
    int A,B;
    cin>>A>>B;
    cout<<A*(A-1)/2+(B-1)*B/2<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    bool judge = true;
    for(int i = 0; i < s.length(); i++){
        if(i % 2 == 0){
            if(!(s[i] == 'R' || s[i] == 'U' || s[i] == 'D')){
                judge = false;
            }
        }else{
            if(!(s[i] == 'L' || s[i] == 'U' || s[i] == 'D')){
                judge = false;
            }
        }
    }
    if(judge){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]
    
    x, y = 0, 0
    check[y][x] = True
    while True:
        fin = True
        for nx, ny in [(x+1, y), (x, y+1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if a[ny][nx] == "#":
                    check[ny][nx] = True
                    fin = False
                    x, y = nx, ny
                    break
        if fin:
            break
    
    ok = False
    if x == W-1 and y == H-1:
        ok = True
        for i in range(H):
            for j in range(W):
                if a[i][j] == "#" and not check[i][j]:
                    ok = False
                    break
            if not ok:
                break

    if ok:
        print("Possible")
    else:
        print("Impossible")



if __name__ == "__main__":
    main()

Measured memory_bytes: 3444
N = int(input())
S = input()

def alpha(a):
  if a == "A":
    a = 1
  elif a == "B":
    a = 2
  elif a == "C":
    a = 3
  elif a == "D":
    a = 4
  elif a == "E":
    a = 5
  elif a == "F":
    a = 6
  elif a == "G":
    a = 7
  elif a == "H":
    a = 8
  elif a == "I":
    a = 9
  elif a == "J":
    a = 10
  elif a == "K":
    a = 11
  elif a == "L":
    a = 12
  elif a == "M":
    a = 13
  elif a == "N":
    a = 14
  elif a == "O":
    a = 15
  elif a == "P":
    a = 16
  elif a == "Q":
    a = 17
  elif a == "R":
    a = 18
  elif a == "S":
    a = 19
  elif a == "T":
    a = 20
  elif a == "U":
    a = 21
  elif a == "V":
    a = 22
  elif a == "W":
    a = 23
  elif a == "X":
    a = 24
  elif a == "Y":
    a = 25
  else:
    a = 26
  return a

def num(a):
  if a == 0:
    a = "A"
  elif a ==1:
    a ="B"
  elif a ==2:
    a ="C"
  elif a ==3:
    a ="D"
  elif a ==4:
    a ="E"
  elif a ==5:
    a ="F"
  elif a ==6:
    a ="G"
  elif a ==7:
    a ="H"
  elif a ==8:
    a ="I"
  elif a ==9:
    a ="J"
  elif a ==10:
    a ="K"
  elif a ==11:
    a ="L"
  elif a ==12:
    a ="M"
  elif a ==13:
    a ="N"
  elif a ==14:
    a ="O"
  elif a ==15:
    a ="P"
  elif a ==16:
    a ="Q"
  elif a ==17:
    a ="R"
  elif a ==18:
    a ="S"
  elif a ==19:
    a ="T"
  elif a ==20:
    a ="U"
  elif a ==21:
    a ="V"
  elif a ==22:
    a ="W"
  elif a ==23:
    a ="X"
  elif a ==24:
    a ="Y"
  else:
    a = "Z"
  return a

ll = [0] * len(S)
for i in range(len(S)):
  b = 0
  b = alpha(S[i]) - 1
  b = (b + N) % 26
  c = num(b)
  ll[i] = c
  
print("".join(ll))

Measured memory_bytes: 3316
import itertools
n, m, q = map(int, input().split())
values = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp = 0
    for a, b, c, d in values:
        if comb[b - 1] - comb[a - 1] == c: tmp += d
    ans = max(tmp, ans)
print(ans)

Measured memory_bytes: 9056
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)
int a[100010];
int main(){
    int h, n;
    cin >> h >> n;
    rep(i, 0, n) cin>>a[i];
    rep(i, 0, n) h -= a[i]; 
    if(0 < h) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
	static ArrayList<Edge>[] list;
	static long[] dist;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		list=new ArrayList[n+1];
		dist=new long[n+1];
		for(int i = 0; i<=n; i++){
			list[i]=new ArrayList<>();
		}
		for(int i = 0; i<n-1; i++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			long c = sc.nextLong();
			list[a].add(new Edge(b,c));
			list[b].add(new Edge(a,c));
		}
		int q = sc.nextInt();
		int k = sc.nextInt();
		dfs(k,0,-1);
		for(int i = 0; i<q; i++){
			int x = sc.nextInt();
			int y = sc.nextInt();
			System.out.println(dist[x]+dist[y]);
		}
	}
	static void dfs(int now,long cost,int front){
		dist[now]=cost;
		for(Edge i:list[now]){
			if(i.to!=front){
				dfs(i.to,i.cost+cost,now);
			}
		}
	}
	
	static class Edge{
		int to;
		long cost;
		public Edge(int to,long cost){
			this.to=to;
			this.cost=cost;
		}
	}
}


Measured memory_bytes: 189948
import java.util.*;
public class Main {
	public static void main(String[] args){
		
		
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();

		// 出力
		System.out.println(  ((a+b)*h)/2   );
		
		
	}
}

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

const ll mod = 998244353;

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

  vector<int> d(n);
  for (int i = 0; i < d.size(); ++i)
    cin >> d[i];

  if (d.front() != 0) {
    cout << 0 << endl;
    return 0;
  }

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

  ll ans = 1;
  ll cnt_p = 1; // parent
  ll cnt_c = 0; // child
  int depth = 1;

  auto f = [&]() {
    ll tmp = 1;
    for (int i = 0; i < cnt_c; ++i)
      tmp = tmp * cnt_p % mod;
    ans = ans * tmp % mod;
  };

  for (int i = 1; i < d.size(); ++i) {
    if (d[i] == depth) {
      ++cnt_c;
      continue;
    }
    if (d[i] != depth + 1) {
      ans = 0;
      break;
    }
    f();
    cnt_p = cnt_c;
    cnt_c = 1;
    depth = d[i];
  }
  if (ans != 0)
    f();

  cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

int main(){
    int n;
    while(cin >> n && n){
        vector<int> a(n);
        vector<bool> c(n);
        REP(i, n) {
            string s;
            cin >> s;
            if(s == "x"){
                c[i] = true;
            }else{
                a[i] = stoi(s);
            }
        }
        set<int> ans;
        REP(j, n){
            REP(dx, 5){
                int x = a[j] + dx - 2;
                REP(i, n) if(c[i]) a[i] = x;
                bool ok = true;
                REP(i, n - 1){
                    if(i % 2 == 0 && a[i] >= a[i + 1]) ok = false;
                    if(i % 2 == 1 && a[i] <= a[i + 1]) ok = false;
                }
                if(ok){
                    ans.insert(x);
                }
            }
        }
        if(ans.size() == 1) cout << *ans.begin() << endl;
        else if(ans.size() == 0) cout << "none" << endl;
        else cout << "ambiguous" << endl;
    }
    return 0;
}

Measured memory_bytes: 1412
#include<bits/stdc++.h>
using namespace std;
int main(){
  char a,b;
  cin>>a>>b;
    if ((int)a>(int)b) cout<<">"<<endl; 
    if ((int)a<(int)b) cout<<"<"<<endl; 
    if ((int)a==(int)b) cout<<"="<<endl; 

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  for (int i = 0; i < s.size(); i++) {
  	if (s[i] == 'R') n--;
  }
  if (n < (s.size() + 1) / 2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, wlim = list(map(int,ipti().split()))
    w = [0] * n
    v = [0] * n

    for i in range(n):
        w[i], v[i] = list(map(int,ipti().split()))

    dp = [[0] * (wlim+1) for _ in range(n+1)]

    for i in range(n):
        vcur = v[i]
        wcur = w[i]
        for j in range(wlim + 1):
            if wcur <= j:
                dp[i+1][j] = max(dp[i][j-wcur] + vcur, dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[n][wlim])


if __name__ == '__main__':
    main()

Measured memory_bytes: 119024
#include <iostream>
#include <cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef pair<double,double>P_D;
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define ALL(a)  (a).begin(),(a).end()
#define MAX 100100
#define MAX_N 200100
#define SENTINEL 2000000000
#define NIL -1
const int MOD = 1e9+7;
const int INF = 1 << 29;
const ll INFTY=1000000000000000000LL;
ll n,T[5],temp;
int main(){
    cin>>n;
    rep(i,5){
        cin>>temp;
        T[i]=(n-1)/temp;
    }
    cout<<*max_element(T,T+5)+5<<endl;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
sum_a = [0]*(n+1)
count = 0
for i in range(0,n):
  sum_a[i+1]=a[i]+sum_a[i]
  if i%2==0:
    if sum_a[i+1]>0:
      continue
    else:
      count += 1+abs(sum_a[i+1])
      sum_a[i+1]=1    
  else: 
    if sum_a[i+1]<0:
      continue
    else:
      count += 1+abs(sum_a[i+1])
      sum_a[i+1]=-1

ans = count
sum_a = [0]*(n+1)
count = 0
for i in range(0,n):
  sum_a[i+1]=a[i]+sum_a[i]
  if i%2==1:
    if sum_a[i+1]>0:
      continue
    else:
      count += 1+abs(sum_a[i+1])
      sum_a[i+1]=1    
  else: 
    if sum_a[i+1]<0:
      continue
    else:
      count += 1+abs(sum_a[i+1])
      sum_a[i+1]=-1

print(min(count,ans))

Measured memory_bytes: 14468
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		Set<String> fruits = new HashSet();
		for(int i = 0; i < N; i++) {
			String line = sc.next();
				fruits.add(line);
		}
		System.out.println(fruits.size());
	}

}


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

int main(int argc, char const *argv[])
{
	int h,w;
	cin>>h>>w;
	string s[h];
	for (int i = 0; i < h; ++i)
	{
		cin>>s[i];
	}
	int l[h+5][w+5]={},r[h+5][w+5]={},u[h+5][w+5]={},d[h+5][w+5]={};
	for (int i = 1; i <= h; ++i)
	{
		for (int j = 1; j <= w; ++j)
		{
			l[i][j]=l[i][j-1]+1;
			if (s[i-1].at(j-1)=='#')
			{
				l[i][j]=0;
			}
		}
	}
	for (int i = 1; i <= h; ++i)
	{
		for (int j = w; j > 0; --j)
		{
			r[i][j]=r[i][j+1]+1;
			if (s[i-1].at(j-1)=='#')
			{
				r[i][j]=0;
			}
		}
	}
	for (int i = 1; i <= h; ++i)
	{
		for (int j = 1; j <= w; ++j)
		{
			u[i][j]=u[i-1][j]+1;
			if (s[i-1].at(j-1)=='#')
			{
				u[i][j]=0;
			}
		}	
	}
	for (int i = h; i > 0; --i)
	{
		for (int j = w; j > 0; --j)
		{
			d[i][j]=d[i+1][j]+1;
			if (s[i-1].at(j-1)=='#')
			{
				d[i][j]=0;
			}
		}
	}
	int ans=0;
	for (int i = 1; i <= h; ++i)
	{
		for (int j = 1; j <= w; ++j)
		{
			ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 67200
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    w = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    e = [(dat[i*3+2], dat[i*3] - 1, dat[i*3+1] - 1) for i in xrange(m)]
    e.sort()
    p = range(n)
    ok = [0] * m
    h = [None] * n
    g = [tuple() for i in xrange(m)]
    st = []
    pu = st.append
    for i, z in enumerate(e):
        c, u, v = z
        x = u
        while x != p[x]:
            pu(x)
            x = p[x]
        pu(x)
        t = x
        x = v
        while x != p[x]:
            pu(x)
            x = p[x]
        for y in st:
            p[y] = x
        del st[:]
        if x != t:
            w[x] += w[t]
            if w[x] >= c:
                ok[i] = 1
            g[i] = (h[x], h[t])
            h[x] = i
        else:
            if w[x] >= c:
                ok[i] = 1
            g[i] = (h[x],)
            h[x] = i
    d = [0] * m
    po = st.pop
    for i in xrange(m - 1, -1, -1):
        if d[i]:
            continue
        pu(i)
        while st:
            x = po()
            d[x] = 1
            for y in g[x]:
                if y is not None:
                    ok[y] |= ok[x]
                    pu(y)
    print m - sum(ok)
main()


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

m = int(((sum(a)/n)*2 + 1) //2)
# m = statistics.mean(a)
# m = int(m) + 1 if m % 1 > 0.5 else int(m)
r = 0
for i in a:
  r += (i - m)**2
  
print(r)


Measured memory_bytes: 5080
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

// auto mod int
const int mod = 1e9 + 7;
struct mint{
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint fastpow(ll n){
  if (n == 0) return 1;
  mint x = fastpow(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}

mint nCr(ll n, ll r){
  mint x = 1, y = 1;
  REP(i, r){
    x *= n - i;
    y *= i + 1;
  }
  return x / y;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, a, b; cin >> n >> a >> b;
  mint ans = fastpow(n);
  ans -= 1;
  ans -= nCr(n, a);
  ans -= nCr(n, b);
  cout << ans.x << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <sstream>
#include <deque>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdio>
const int M = 1e9 + 7;
#define ll long long int
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
using namespace std;

//insta  -------  __ansh7
//MSDIAN

// Basic Template

int main()
{
    fastio

    ll n,k;
    cin>>n>>k;

    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }

    sort(a,a+n);

    ll sum=0;

    for(ll i=0;i<k;i++)
    {
        sum=sum+a[i];

    }

    cout<<sum;



 

        return 0;
    }

Measured memory_bytes: 3556
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;
const int INF = 10000000;

int main(){
    int a, b, c; cin >> a >> b;
    c = a + b;

    if(a % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }else if(b % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }else if((a + b) % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }
    cout << "Impossible" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    HashSet<Integer> cards = new HashSet<Integer>();
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    for(int i = 0; i < num; i++) {
      cards.add(sc.nextInt());
    }
    int res = cards.size();
    if(res % 2 == 0) res--;
    System.out.println(res);
  }
}

Measured memory_bytes: 51972
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, x;
  cin>>n;
  if(n % 1000 == 0) cout<<"0";
  else{
  x=1000- (n % 1000);
  cout<<x;
}}
  

Measured memory_bytes: 3564
class Item:
	def __init__(self,v,w):
		self.v=v
		self.w=w
		self.r=v/w

n,w=map(int,input().split())
items=[]
for i in range(n):
	vi,wi=map(int,input().split())
	items.append(Item(vi,wi))
	
items.sort(key=lambda x:x.r,reverse=True)

total=0
remain = w
for i in range(n):
	vi = items[i].v
	wi = items[i].w
	ri = items[i].r
	if wi <= remain:
		total += vi
		remain -= wi
	else:
		total += ri * remain
		break
			
print(total)



Measured memory_bytes: 32556
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//---------------------------------------------------------------------------------------------------
ll MOD = 998244353;
ll f[301010], rf[301010];
ll inv(ll x) {
    ll res = 1;
    ll k = MOD - 2;
    ll y = x;
    while (k) {
        if (k & 1) res = (res * y) % MOD;
        y = (y * y) % MOD;
        k /= 2;
    }
    return res;
}
void init() {
    f[0] = 1;
    for(int i = 1; i < 301010; i++) f[i] = (f[i - 1] * i) % MOD;
    for(int i = 0; i < 301010; i++) rf[i] = inv(f[i]);
}
ll C(int n, int k) {
    if(n < k) return 0;
    ll a = f[n]; // = n!
    ll b = rf[n-k]; // = (n-k)!
    ll c = rf[k]; // = k!

    ll bc = (b * c) % MOD;

    return (a * bc) % MOD;
}
//---------------------------------------------------------------------------------------------------

void add(ll &a, ll b)
{
    a = (a+b) % MOD;
}

int main()
{
    init();
    ll n, a, b, k;
    cin >> n >> a >> b >> k;

    ll ans = 0;
    for(int i = 0; i <= n; i++)
    {
        ll v = k - a*i;
        if(v < 0 || v % b != 0) continue;
        ll num = v / b;
        add(ans, C(n, i) * C(n, num));
    }
    cout << (ans+MOD)%MOD << endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=5005;
const int mo=1000000007;
int n,tot,head[N],f[N];
int g[N][N],sz[N],tmp[N];
struct edge{
	int to,next;
}e[N*2];
void add(int x,int y){
	e[++tot]=(edge){y,head[x]};
	head[x]=tot;
}
void dfs(int x,int fa){
	g[x][1]=sz[x]=1;
	for (int i=head[x];i;i=e[i].next)
		if (e[i].to!=fa){
			dfs(e[i].to,x);
			for (int j=sz[x]&1;j<=sz[x];j+=2)
				for (int k=sz[e[i].to]&1;k<=sz[e[i].to];k+=2)
					tmp[j+k]=(tmp[j+k]+1ll*g[x][j]*g[e[i].to][k])%mo;
			sz[x]+=sz[e[i].to];
			for (int j=sz[x]&1;j<=sz[x];j+=2)
				g[x][j]=tmp[j],tmp[j]=0;
		}
	if (sz[x]%2==0)
		for (int j=2;j<=sz[x];j+=2)
			g[x][0]=(g[x][0]+mo-1ll*g[x][j]*f[j]%mo)%mo;
}
int main(){
	scanf("%d",&n);
	f[0]=1;
	for (int i=2;i<=n;i+=2)
		f[i]=1ll*f[i-2]*(i-1)%mo;
	For(i,1,n-1){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	dfs(1,0);
	int ans=0;
	for (int i=2;i<=n;i+=2)
		ans=(ans+1ll*g[1][i]*f[i])%mo;
	printf("%d\n",ans);
}

Measured memory_bytes: 97152
#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N=10000;
string s,t;

int main(){
	cin >> s;
	for(int i=0;i<s.length();i++){
		if(i%2==0) cout << s[i];
	}
	
	cout << endl;
	return 0;
}


Measured memory_bytes: 512
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Security.Cryptography;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        checked {
            object ret = process(new StreamReader(Console.OpenStandardInput()));
            Console.WriteLine(ret);
        }
#endif
    }

    static object process(TextReader input) {
        var n = long.Parse(input.ReadLine());

        long sum = 0;

        foreach(var i in Aliquot(n)) {
            if(i == 1) continue;
            var m = i - 1;
            if (n / m == n % m) sum += m;
        }

        return sum;
    }

    //約数列挙（1とnを含む降順）
    static List<long> Aliquot(long n) {
        if(n==1) return new List<long>{ 1 };

        var ret = new List<long>();
        for (long j = 1; j <= Math.Sqrt(n); j++) {
            if (n % j != 0) continue;
            ret.Add(n/j);
        }
        ret.Add(1);

        return ret;
    }

    static long[] ToIntArray(string strs, int n) {
        var ret = new long[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = long.Parse(spl[i]);
        return ret;
    }
}

Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
	int n;
  	cin>>n;
  	vint h(n+1);
  	REP(i,1,n+1){
      	cin>>h[i];
    }
  	vint dp(n+1,0);
  	REP(i,2,n+1){
      	if(i>2){
          	dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
        }
      	else{
          dp[i]=abs(h[i]-h[i-1]);
        }
      	
    }
  	cout<<dp[n]<<'\n';
    return(0);
}

Measured memory_bytes: 1024
/**
 * @author torith
 * @date 2018-10-15
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;

    int ans = A * X + B * Y;

    if (X <= Y) {
        ans = min(ans, X * 2 * C + (Y - X) * B);
        ans = min(ans, Y * 2 * C);
    }else{
        ans = min(ans, Y * 2 * C + (X - Y) * A);
        ans = min(ans, X * 2 * C);
    }

    cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if(a >= 6 && a <=12){
        cout << b/2 << endl;
    }else if(a <= 5){
        cout << 0 << endl;
    }else{
        cout << b << endl;
    }
}

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

public class Hello{
    public static void Main(){
        string InputNum;
        List<int> Num = new List<int>();
        int MaxNum = 0;
        int TmpNum = 0;
        List<int> Primes = new List<int>();
        bool[] PrimeCheck = Enumerable.Repeat<bool>(true, Consts.MAX_NUM).ToArray();
        
        while((InputNum = Console.ReadLine()) != null){
            TmpNum = int.Parse(InputNum);
            Num.Add(TmpNum);
            MaxNum = MaxNum < TmpNum ? TmpNum : MaxNum;
        }
        
        
        for(int Idx = 0; Idx < Num.Count; Idx++){
            if(Primes.Count == 0){
                for(int i = 0; i < MaxNum; i++){
                    if(i == 0 || i == 1){
                        PrimeCheck[i] = false;
                        continue;
                    }
                    else if(PrimeCheck[i] == false){
                        continue;
                    }
                    else{
                        Primes.Add(i);
                        for(int n = i * 2; n < MaxNum; n += i){
                            PrimeCheck[n] = false;
                        }
                    }
                }
            }
            
            for(int i = 0; i < Primes.Count; i++){
                if(Num[Idx] < Primes[i]){
                    System.Console.WriteLine(i);
                    break;
                }
                if(i == Primes.Count -1){
                    System.Console.WriteLine(Primes.Count);
                }
            }
        }
    }
}

public static class Consts{
    public static int MAX_NUM = 999999;
}

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


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define pb push_back
#define mp make_pair
#define snd second
#define fst first
#define debug printf("--%d--\n",__LINE__)
#define ll long long int

int main(void){
	string s; int K, N;
	cin >> s;
	N = s.size();
	cin >> K;
	
	for(int i=0;i<N;i++){
		int d = ('a'+26-s[i])%26;
		if (K >= d){
			s[i] = 'a';
			K -= d;
		}
	}
	s[N-1] = 'a' + (s[N-1]-'a' + K%26)%26;
	cout << s << endl;
	
	
	return 0;
}


Measured memory_bytes: 512