akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<string,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
map<string,int> m;
string start="01234567";
int d[4]={1,-1,4,-4};
void bfs()
{
	queue<string> q;
	q.push(start);
	m[start]=0;
	while(!q.empty())
	{
		string a=q.front();
		q.pop();
		int pos=a.find("0");
		for(int i=0;i<4;i++)
		{
			string tmp=a;
			if(pos%4==0&&i==1)continue;
			if(pos%4==3&&i==0)continue;
			int nx=pos+d[i];
			if(!(nx>=0&&nx<=7))continue;
			swap(tmp[pos],tmp[nx]);
			if(m.find(tmp)!=m.end())continue;
			m[tmp]=m[a]+1;
			q.push(tmp);
		}
	}
	return;
}
int main()
{
	string s;
	bfs();
	while(getline(cin,s))
	{
		s.erase(remove(s.begin(),s.end(),' '),s.end());
		cout << m[s] << endl;
	}
	return 0;
}

Measured memory_bytes: 3432
'''
エディトリアル
https://atcoder.jp/img/agc016/editorial.pdf

解説動画
https://youtu.be/kdQtQSgIYPI?t=20m17s

シミュレーション
'''

s = input()
a = [chr(x) for x in range(97, 97 + 25 + 1)]

'''
a: chr(97)
z: chr(97 + 25)
'''

cnt = float('inf')
for c in a:
    if c in s:
        t = s[:]
        t_cnt = 0
        while len(t) != t.count(c):
            b = ''
            for i in range(len(t) - 1):
                b += c if (t[i] == c) or (t[i + 1] == c) else t[i]
            t = b
            t_cnt += 1
        cnt = min(cnt, t_cnt)
print(cnt)

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n,k,s; cin >> n >> k >> s;
  vector<int> v(n);
  for(int i = 0; i < n; ++i){
    if(s == 1000000000){
      if(i < k)v[i] = s;
      else v[i] = 1;
    } else {
      if(i < k)v[i] = s;
      else v[i] = s + 1;
    }
  }
  for(int i = 0; i < n; ++i)cout << v[i] << endl;
}


Measured memory_bytes: 3776
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)

for i in range (0, M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

print(uf.group_count()-1)

Measured memory_bytes: 13028
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
  
struct P{
  int team;
  int ans;
  int sum;
  int pro[100];
  static bool less(const P& left,const P& right){
    if(left.ans!=right.ans) return left.ans > right.ans;
    else if(left.sum!=right.sum)return  left.sum < right.sum;
    else return left.team < right.team;
  }
};
  
int main(){
  int t,p,r,tid,pid,time;
  string sta;
  while(cin >> t >> p >> r){
    if(t == 0 && r == 0 && p == 0) break;
    vector <P> data;
    P tmp;
    for(int i=0;i<t;i++){
      tmp.team = i+1;
      tmp.ans = 0;
      tmp.sum = 0;
      for(int j=0;j<=p;j++) tmp.pro[j] = 0;
      data.push_back(tmp);
    }
    while(r--){
      cin >> tid >> pid >> time >> sta;
      if(sta == "CORRECT"){
    for(int i=0;i<t;i++){
      if(data[i].team == tid){
        data[i].sum += data[i].pro[pid]*1200+time;
        data[i].ans += 1;
        break;
      }
    }
      }
      else if(sta == "WRONG"){
    for(int i=0;i<t;i++){
      if(data[i].team == tid) data[i].pro[pid] += 1;
    }
      }
    }
    sort(data.begin(),data.end(),P::less);
    for(int i=0;i<t;i++) cout << data[i].team << " " << data[i].ans << " " << data[i].sum << endl;
  }
}


Measured memory_bytes: 3236
#include<vector>
#include<iostream>
#include<algorithm>                
#include<string.h>                 
#include<bits/stdc++.h>            
#include<cstring>                  
#include<map>                     
#include<cmath>                  
#include<set>
using namespace std;            
#define ll long long int        
#define ld long double
#define MOD 1000000007 
#define PI 3.1415926535897932384626433832795                                               
#define YY cout<<"YES"
#define NN cout<<"NO"
#define ee cout<<"\n"
#define ne cout<<"-1"
#define pb push_back 
#define fi first
#define se second
#define mkp make_pair    
#define sall(v ) sort(v.begin(), v.end())      
#define all(v )  v.begin(), v.end()      
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#define vl vector<ll>
#define vll vector< pair<ll,ll> > 
#define mpl map<ll, ll>
#define pr pair<ll,ll>
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) {return (a.second < b.second); }
ll pow1(ll n,ll p){if(p==0)return 1;ll x=pow1(n, p/2);x=(x*x)%MOD;if(p%2==0) return x%MOD;else return (x*n)%MOD;}
ll pd(ll x,ll y){if(x%y==0) return x/y;else return x/y+1;}  
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);	
	  ll t=1;
 
 
//	   cin>>t;
	      while(t--)
{
//SUN, MON, TUE, WED, THU, FRI, or SAT.
ll n;
string s;
cin>>s;
if(s=="SUN")	
cout<<7;
else if(s=="MON")	
cout<<6;
else if(s=="TUE")	
cout<<5;
else if(s=="WED")	
cout<<4;
else if(s=="THU")	
cout<<3;
else if(s=="FRI")	
cout<<2;
else if(s=="SAT")	
cout<<1;
	
}
return 0;
}
 
 

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		
		System.out.println(Math.min(a,  b) + Math.min(c,  d));
	}
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;

//購入可能な個数n個の最大円... 5n;


int main(){
  int x;
  cin >>x;
  int n,zeni;
  int ans=0;
  
  n=x/100;
  while(n>0){
  	zeni=x-100*n;//小銭金額
    if(zeni<=5*n){
      ans=1;
      break;
    }
    
  
  n--;
  }
  if(n==0){
    ans=0;
  }
  
  cout<<ans<<endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#include <fstream>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LL long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
 
int main(){
    int n,m; cin>>n>>m;
    int a,b;
    int sta[200001]={0};
    FOR(i,0,m){
        cin>>a>>b;
        if(a==1){
            sta[b]++;
        }
        if(b==n){
            sta[a]++;
        }
    }
    bool fl=false;
    FOR(i,0,n+1){
        if(sta[i]>=2) fl=true;
    }
    POS(fl);
}

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

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

int main(){
    int K, X;
    cin >> K >> X;
    for(int i = X - K + 1; i <= X + K - 1; i++){
        cout << i << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;

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

		// ex1
		//  0 1
		//  b b
		// -----
		// 1 2 5 
		// 0 1 2
		ll ans = 0;
		for (int bits = 0; bits < (1<<S.size()-1); ++bits) {
				ll x = 0;
				for (int i = 0; i < S.size(); ++i) {
						x += S[i] - '0';
						if (bits & (1<<i)) {
								ans += x;
								x = 0;
						} else {
								if (i == S.size()-1) ans += x;
								else x *= 10;
						}
				}
		}

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


Measured memory_bytes: 256
from itertools import permutations
 
 
def closest_path_lens(idx___neigh_idxes__dists, idx1):
    INF = 100001 * 201 * 200
    nodes_nr = len(idx___neigh_idxes__dists)
    idx___visited = [False] * nodes_nr
    idx___dist = [INF] * nodes_nr
    idx___dist[idx1] = 0
    for _ in range(nodes_nr):
        curr_idx = -1
        curr_dist = INF
        for idx, dist in enumerate(idx___dist):
            if dist < curr_dist and not idx___visited[idx]:
                curr_idx = idx
                curr_dist = dist
        idx___visited[curr_idx] = True
        for neigh_idx, dist in idx___neigh_idxes__dists[curr_idx]:
            # print(curr_dist, dist)
            idx___dist[neigh_idx] = min(idx___dist[neigh_idx], curr_dist + dist)
    return idx___dist
 
 
towns_nr, roads_nr, towns_to_visit_nr = (int(x) for x in input().split())
towns_to_visit = [(int(x) - 1) for x in input().split()]
town_idx___neigh_idxes__dists = [set() for _ in range(towns_nr)]
for road_idx in range(roads_nr):
    idx1, idx2, dist = (int(x) for x in input().split())
    idx1 -= 1
    idx2 -= 1
    town_idx___neigh_idxes__dists[idx1].add((idx2, dist))
    town_idx___neigh_idxes__dists[idx2].add((idx1, dist))
ttv_idx___ttv_idx__dist = []
for ttv in towns_to_visit:
    town_idx___dist  = closest_path_lens(town_idx___neigh_idxes__dists, ttv)
    # print(town_idx___dist)
    ttv_idx___dist = [town_idx___dist[idx] for idx in towns_to_visit]
    # print(ttv_idx___dist)
    ttv_idx___ttv_idx__dist.append(ttv_idx___dist)
ans = 100001 * 201 * 200
for path in permutations(list(range(towns_to_visit_nr))):
    curr_ans = 0
    curr_idx = path[0]
    for ttv_idx in path:
        # print(curr_idx, ttv_idx)
        curr_ans += ttv_idx___ttv_idx__dist[curr_idx][ttv_idx]
        curr_idx = ttv_idx
    # print(curr_ans)
    # print('\n')
    ans = min(ans, curr_ans)
print(ans)
    

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

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    int d = a/b;
    int r = a%b;
    double f = double(a)/b;
    cout << d << " " << r <<" " << fixed << setprecision(10) << f<<endl;
}



Measured memory_bytes: 3272
#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
using base = complex<double>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M 1000000007
#define M2 998244353
#define ll long long
#define pll pair<long, long>
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define REPI(i, a, b) for (ll i = b - 1; i >= a; i--)
#define ff first
#define ss second
#define pb push_back
#define db pop_back
#define mp make_pair
#define mt make_tuple
#define g(a, b) get<a>(b)
#define INF (ll)1e18 + 100
#define vl vector<ll>
#define vi vector<int>
#define vll vector<pair<ll, ll>>
#define vii vector<pair<int, int>>
#define all(v) v.begin(), v.end()
#define bset(a, p) ((a) | (1ll << (p)))
#define bchk(a, p) ((a) & (1ll << (p)))
#define bxor(a, p) ((a) ^ (1ll << (p)));
#define brem(a, p) (bchk(a, p) ? (bxor(a, p)) : (a))
#define INT_SIZE 32

void solve() {
	ll a, b;
	char x;
	cin >> a >> x >> b;
	if (x == '+') {
		cout << a + b;
	}
	else {
		cout << a - b;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	ll ntc;
	// cin >> ntc;
	ntc = 1;
	REP(tc, 1, ntc + 1)
	{
		// cout << "Case #" << tc << ": ";
		solve();
	}
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(ll) (n);i++)
int main(void){
    ll p=0,b[10010],n,m,c,a[1000][1000],co=0;
    double r;
    cin >> r;
    r=r*r*3.14;
    r=r/3.14;
    cout << r << endl;
    return 0;

}


Measured memory_bytes: 3792
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif
int n,gn;
vector<string> res;
void print(){
  R(i,gn){
    cout << res[i] << "\n";
  }
  exit(0);
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  
  cin >> n;
  gn = n;
  if(n <= 2){
    cout << "-1\n";
    return 0;
  }
  res.resize(n,string(n,'.'));
  if(n == 3){
    for(int i = 0; i < n; i+=3){
      res[i][i] = res[i+1][i] = 'a';
      res[i+2][i+2] = res[i+2][i+1] = 'b';
    }
    print();
  }
  if(n == 7){
    res = {
      "aabbaa.",
      "c..c..a",
      "c..c..a",
      ".dd.ddb",
      "c..c..b",
      "c..c..a",
      ".dd.dda"};
    print();
  }
  if(n % 2 == 1){
    vector<string> qq = {
      "aabba",
      "bc..a",
      "bc..b",
      "a.ccb",
      "abbaa",
    };
    R(i,5)R(j,5){
      res[n - i - 1][n - j - 1] = qq[i][j];
    }
    n -= 5;
  }
  vector<string> xx = {
    "aacd",
    "bbcd"
  };
  for(int i = 0; i < n; i+=2){
    R(j,2)R(k,4){
      res[(i + j) % n][(i + k) % n] = xx[j][k];
    }
  }
  print();
  
}


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

int main(){
  long a,b;
  int i,j;
  long tmp_a,tmp_b;
  
  cin >> a >> b;
  
  for(i=1;i<=b;i++){
    if(a*i/b != 0 && a*i % b ==0){
      tmp_a = a * i;
      break;
    }
  }
  for(i=1;i<=a;i++){
    if(b*i/a != 0 && b*i % a ==0){
      tmp_b = b * i;
      break;
    }
  }
  
  cout << min(tmp_a, tmp_b) << '\n';
  
  return 0;
  
}


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

#define INPUT_FROM_FILE (0) 
#if INPUT_FROM_FILE
#include <fstream>
#endif

int main(int argc, char **argv){
	double h;
	double min_h = 1000001;
	double max_h = 0;

#if INPUT_FROM_FILE
	//std::ifstream ifs("test.txt");
	FILE *fp = fopen("test.txt", "r");
#endif

	
#if INPUT_FROM_FILE
	while(fscanf(fp, "%lf", &h) != EOF){
#else
	while(scanf("%lf", &h) != EOF){
#endif
		min_h = std::min(min_h, h);
		max_h = std::max(max_h, h);
	}
	double dif = int((max_h - min_h) * 100 + 0.5) / 100.0;
	std::cout << dif << std::endl;
	return 0;
}



Measured memory_bytes: 3192
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

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

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

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    int A,B;
    string S;
    string ans="Yes";

    cin >> A >> B >> S;

    for(int i=0; i<A+B+1; i++){
        if(i!=A){
            if(S[i]<'0' || S[i]>'9') ans="No";
        }else{
            if(S[i]!='-') ans="No";
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <numeric>
#include <set>
#include <unordered_set>
#include <queue>
#include <boost/math/constants/constants.hpp>
#include <boost/math/common_factor_rt.hpp>
 
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, n, m) for(int i=n; i<m; ++i)
 
int main() {
  string S;
  cin >> S;
  

  

    if(S[2]==S[3] && S[4]==S[5]){
	  cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  
  
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SWAP(type, x, y) do { type tmp = x; x = y; y = tmp; } while (0)

#define MOD 1000000007 

int main(void){
    int A,B,C,X,Y;
    scanf("%d%d%d%d%d",&A,&B,&C,&X,&Y);

    long ans=0;
    if(A+B>2*C) ans+=2*C*MIN(X,Y);
    else ans+=(A+B)*MIN(X,Y);

    if(X>Y){
        if(A>2*C) ans+=2*C*(X-Y);
        else ans+=A*(X-Y);
    }
    else{
        if(B>2*C) ans+=2*C*(Y-X);
        else ans+=B*(Y-X);
    }
    printf("%ld\n",ans);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<utility>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef pair<int,int> p;
typedef pair<int,p> pip;

int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		int pin,din;
		pip d[n];
		rep(i,n){
			cin>>din>>pin;
			d[i]=pip(pin,p(din,i));
		}
		sort(d,d+n);
		for(int i=n-1;i>=0;i--){
			if(d[i].second.first<=m){
				m-=d[i].second.first;
				d[i].second.first=0;
			}else{
				d[i].second.first-=m;
				m=0;
			}
			if(m<=0)break;
		}
		int sum=0;
		rep(i,n){
			sum+=d[i].second.first*d[i].first;
		}
		cout<<sum<<endl;
	}
	return 0;
}

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

void solve(int n, int w, long long int arr[][2]){
    long long int dp[n+1][w+1];
    for(int i = 0; i <= n; i++)dp[i][0] = 0;
    for(int i = 0; i <= w; i++)dp[0][i] = 0;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= w; j++){
            if(arr[i-1][0] > j)dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i-1][0]]+arr[i-1][1]);
            }
        }
    }
    cout<<dp[n][w];
}

int main() {
	int n,w;
	cin>>n>>w;
	long long int arr[n][2];
	for(int i = 0; i < n; i++){
	    cin>>arr[i][0]>>arr[i][1];
	}
	solve(n,w,arr);
	return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


int main() {
	int n;
	string s;
	cin >> n >> s;
	int open = 0, close = 0;
	for(int i = 0; i < n; i++){
        if(s[i] == '('){
           open++;
        }
        else{
            if(open > 0) open--;
            else close++;
        }
	}
	while(close--) cout << '(';
	cout << s;
	while(open--) cout << ')';
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int d, n; cin >> d >> n;
  if (n == 100) ++n;
  cout << (long long)pow(100, d) * n << '\n';
  return 0;
}


Measured memory_bytes: 256
N,K = map(int,raw_input().split())
ans = float(0)
tmp = 0
con = 0
for i in range(1,N+1):
  tmp = i
  for j in range(0,K,i):
    if tmp >= K:
      break
    tmp = tmp * 2
    con = con + 1
  ans = ans + (1.0/2.0)**con * (1.0/N)
  con = 0
  tmp = 0
print ans

Measured memory_bytes: 6020
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m, l;
    cin >> n >> m >> l;

    vector<vector<ll>> a(n, vector<ll>(m));
    vector<vector<ll>> b(m, vector<ll>(l));
    vector<vector<ll>> c(n, vector<ll>(l));

    forn(i, n) forn(j, m) cin >> a[i][j];
    forn(i, m) forn(j, l) cin >> b[i][j];

    forn(i, n) {
        forn(j, l) {
            forn(k, m) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    forn(i, n) {
        forn(j, l) {
            if(j != 0) cout << " ";
            cout << c[i][j];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  string s;
  cin >> s;
  char c = s.at(s.size()-1);
  string ans;
  if(c=='3') {
    cout << "bon" << endl;
    return 0;
  } else if(c=='0' or c=='1' or c=='6' or c=='8') {cout<<"pon"<<endl;return 0;}
  cout << "hon" << endl;
  

  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
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; }

int main(){
    ll a,b,v,w,t;
    cin >> a>>v>>b>>w>>t;

    ll d=(a<b? b-a:a-b);
    if (d==0) cout << "YES"<<endl;
    else if((v-w)*t>=d) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 

ll power(ll x,ll y,ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;

	cin >> n;
	vector<ll>v,g;
	for(i=1;i<=n;i++)
	{
		cin >> x >> y;
		v.pb(x);
		g.pb(y);
	}

	sort(all(v)),sort(all(g));

	if(n%2)
	{
		i=n/2,j=n/2;

		// k=i;
		// while(k<n && v[k].ff==v[i].ff)
		// 	k++;
		// i=k-1;

		// k=j;
		// while(k>=0 && v[k].ff==v[j].ff)
		// 	k--;
		// j=k+1;

		cout<<g[i]-v[j]+1<<endl;
	}
	else
	{
		i=n/2,j=n/2-1;


		y=v[i]+v[j];
		x=g[i]+g[j];

		if(y%2)
		{
			if(x%2)
			{
				cout<<(x/2-y/2+1)*2-1<<endl;
			}
			else
			{
				cout<<(x/2-y/2+1)*2-2<<endl;

			}
		}
		else
		{
			if(x%2)
			{

				cout<<(x/2-y/2+1)*2<<endl;
			}
			else
			{
				cout<<(x/2-y/2+1)*2-1<<endl;

			}
		}
	}
}

Measured memory_bytes: 6676
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int N, K;
ll A[202020], AS[202020];
map<ll, int> cm;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    for (int i = 0; i < N; ++i) { cin >> A[i]; --A[i]; }

    ll ans = 0;
    cm[0] = 1;
    AS[0] = 0;
    for (int i = 1; i <= N; ++i) {
        if (i-K >= 0) cm[AS[i-K] % K]--;
        AS[i] = (AS[i-1] + A[i-1]) % K;
        ans += cm[AS[i]]++;

    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 15872
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

N, M = map(int, input().split())
a = [int(x)//2 for x in input().split()]
m = 1
while a[0] % (m<<1) == 0:
    m <<= 1
for x in a[1:]:
    if x % m != 0:
        print(0)
        exit()
    elif x % (m<<1) == 0:
        print(0)
        exit()
gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
lcm = 1
for x in a:
    lcm = lcm * x // gcd(x, lcm)
l, r = 0, 10**9
while l+1 < r:
    m = (l+r)//2
    if m * lcm > M:
        r = m
    else:
        l = m
if l % 2 == 0:
    if (l+1) * lcm <= M:
        print((l+2)//2)
    else:
        print(l//2)
else:
    print((l+2)//2)


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

int n,k;
int hi[100080],dp[100080];


int main()
{
	ios::sync_with_stdio("false");
//	freopen(".in","r",stdin);
//	freopen(".out","r",stdout);
	cin>>n>>k;
	memset(dp,0x3f3f3f3f,sizeof(dp));
	for(register int i=1;i!=n+1;++i)
		cin>>hi[i];
		
	dp[1]=0;
	for(register int i=1;i!=n+1;++i)
	{
		for(register int j=1;j!=k+1 && j+i!=n+1;++j)
			dp[i+j]=min(dp[i+j],dp[i]+abs(hi[i]-hi[i+j]));
	}
	cout<<dp[n]<<"\n";
	
	
	return 0;
}


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


using namespace std;


int sqr(int x)
{   return x*x;
}


float dis(pair<int,int> a, pair <int,int> b)
{
    return sqrt( sqr(a.first - b.first)+sqr(a.second - b.second));
}

int main()
{


int n;
cin >> n;
vector <pair<int,int>> a(n);
for (int i=0; i<n; i++){ cin >> a[i].first >> a[i].second;}

float sum = 0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            sum+= dis(a[i],a[j]);
sum/=n;

//for (int i=2; i<=n; i++){ sum*=2; sum/=i;}
printf("%.10f",sum);








}























Measured memory_bytes: 256
class twoD_cumsum():
    # da[i][j]:(0,0)~(i,j)の長方形の和
    def __init__(self,h,w,a):
        self.h = h; self.w = w
        self.da = a
        for i in range(1, w):
            self.da[0][i] = self.da[0][i - 1] + a[0][i]
        for i in range(1, h):
            cnt_w = 0
            for j in range(w):
                cnt_w += a[i][j]
                self.da[i][j] = self.da[i - 1][j] + cnt_w
    def da_generate(self, da):
        return da
    # da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
    def da_calc(self, p, q, x, y):
        if p > x or q > y:
            return 0
        if p == 0 and q == 0:
            return self.da[x][y]
        if p == 0:
            return self.da[x][y] - self.da[x][q - 1]
        if q == 0:
            return self.da[x][y] - self.da[p - 1][y]
        return self.da[x][y] - self.da[p - 1][y] - self.da[x][q - 1] + self.da[p - 1][q - 1]

def examD():
    N, K = LI()
    #y=0,x=0上で、原点とおなじグループかどうか
    colorXY = [[0] * (2*K) for _ in range(2*K)]
    for _ in range(N):
        #原点の色を白(0)とする
        x, y, c = LSI()
        x, y = int(x), int(y)
        if c=="B":
            y +=K
        colorXY[x%(2*K)][y%(2*K)] +=1
    ans = 0
    ansC = N
    da = twoD_cumsum(2*K, 2*K, colorXY)
    for i in range(K):
        for j in range(K):
            cur = da.da_calc(0,0,K-i-1,K-j-1) + da.da_calc(K-i,K-j,2*K-i-1,2*K-j-1)\
                + da.da_calc(0,2*K-j,K-i-1,2*K-1) + da.da_calc(2*K-i,0,2*K-1,K-j-1)\
                + da.da_calc(2*K-i,2*K-j,2*K-1,2*K-1)
            ans = max(ans,cur)
            ansC = min(ansC,cur)
    print(max(ans,N-ansC))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


Measured memory_bytes: 77020
#include<stdio.h>
int main(){
	int n[5],i,m=1;
	for(i=0;i<5;i++)scanf("%d",&n[i]);
	i=1;
	while(n[0]>n[1]*m)++m;
	while(n[0]>n[3]*i)++i;
	n[2]*=m,n[4]*=i;
	if(n[2]>n[4])n[2]=n[4];
	printf("%d\n",n[2]);
	return 0;
}


Measured memory_bytes: 2080
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll N; cin >> N;
    vvll e(N+1, vll(0));
    vector<P> h(0);
    rep(i, 0, N-1){
        ll a, b; cin >> a >> b;
        e[a].emplace_back(b);
        e[b].emplace_back(a);
        h.emplace_back(P(max(a,b), min(a,b)));
    }
    vll c(N);
    ll s = 0;
    rep(i, 0, N){
        cin >> c[i];
        s += c[i];
    }
    sort(c.begin(),c.end(),greater<ll>());
    vll num(N+1);
    num[1] = c[0];
    queue<ll> q;
    for(auto x:e[1]){
        q.push(x);
    }
    vb ald(N+1, false);
    ald[1] = true;
    ll t = 1;
    while(!q.empty()){
        ll a = q.front();
        ald[a] = true;
        num[a] = c[t];
        q.pop();
        for(auto x: e[a]){
            if(!ald[x]){
                q.push(x);
            }
        }
        t++;
    }
    prtl(s-c[0]);
    rep(i, 1, N+1){
        prt(num[i]); prt(" ");
    }
}

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

int main() {
  int x,y; cin>>x>>y;
  if(x*2==y||x*4==y)
    cout<<"Yes"<<endl;
  else{
    if((x*4-y)%2==0&&x*4>y){
      if((x*4-y)/2<x)
        cout<<"Yes"<<endl;
      else
        cout<<"No"<<endl;
    }
    else
      cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3556
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using uint64 = unsigned long long;
using vi = std::vector<int>;
using vl = std::vector<int64>;
using pii = std::pair<int, int>;
using pii = std::pair<int, int>;
using pll = std::pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(_) (_).begin(), (_).end()
#define rall(_) (_).rbegin(), (_).rend()
#define print(_) std::cout << (_) << '\n'
#define debug(_) std::cerr << #_ << ": " << (_) << '\n'
#define dbg(vec) for (size_t _ = 0; _ < vec.size(); ++_){std::cerr << #vec << "[" << _ << "] : " << vec[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;  // 1.073741823e9
const int64 INF64 = (1LL<<62) - 1;  // 4.611686018427387903e18
const int MOD = 1000000007;

vector<int> graph[202020];
vector<int> score(202020);

void dfs(int source, int prev = -1) {
  for (int next : graph[source]) {
    if (next == prev) continue;
    score[next] += score[source];
    dfs(next, source);
  }
}

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

  int n, q; cin >> n >> q;
  for (int i = 0; i < n - 1; ++i) {
    int a, b; cin >> a >> b;
    --a; --b;
    graph[a].emplace_back(b);
    graph[b].emplace_back(a);
  }

  for (int i = 0; i < q; ++i) {
    int p, x; cin >> p >> x;
    --p;
    score[p] += x;
  }

  dfs(0);

  for (int i = 0; i < n; ++i) {
    cout << score[i] << " ";
  }
  cout << '\n';

  return 0;
}

Measured memory_bytes: 23552
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> input(N);
  int answer =0;
  bool canDivide = true;
  
  for (int i =0; i < N; i++){
    cin >> input.at(i);
  }
  while(canDivide){
    for (int i =0; i < N; i ++){
      if(input.at(i)%2 != 0){
        canDivide = false;
        break;
      } else {
        input.at(i) /= 2;
      }
    }
    if(canDivide){
      answer++;
    }
  }
  cout << answer << endl;
}


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

int main() {
  int n, k, x, sum;
  sum = 0;
  std::cin >> n >> k;
  for (int i = 0; i < n; i++) {
    std::cin >> x;
    if (x >= k - x) {
      sum += k - x;
    } else {
      sum += x;
    }
  }
  std::cout << sum * 2 << std::endl;
}


Measured memory_bytes: 256
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

a,b = get_nums_l()


print(math.ceil((b-1) / (a-1)))

Measured memory_bytes: 38736
//16D8103013E Sen Shunkou
#include<iostream>
int main(){
    int n;
    std::cin>>n;
    int A[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            A[i][j]=0;
        }
    }
    int tmp,s,e;
    for(int i=0;i<n;i++){
        std::cin>>s;
        std::cin>>tmp;
        for(int j=0;j<tmp;j++){
            std::cin>>e;
            A[s-1][e-1]=1;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j==0){
                std::cout<<A[i][j];
            }else std::cout<<" "<<A[i][j];
        }
        std::cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3120
fn main() {
    proconio::input! {
        a: i32,
        b: i32,
        c: i32,
        d: i32,
    }
    let f=|i:i32,j:i32|(i-j).abs()<=d;
    println!("{}",if f(a,c) || (f(a,b)&&f(b,c)) {"Yes"} else {"No"});
}

Measured memory_bytes: 2084
#include <bits/stdc++.h>
#define ll long long
#define p pair<ll, int>
using namespace std;
const int SIZE = 100005;
const ll INF = 1e18;

struct Edge {
    int to;
    ll cost;
};

ll dist[SIZE];
bool used[SIZE];
vector<Edge> g[SIZE];

void solve(int s) {
    for (int i = 0; i < SIZE; i++) {
        dist[i] = INF;
        used[i] = false;
    }
    dist[s] = 0;
    priority_queue<p, vector<p>, greater<p>> que;
    que.push(p(0, s));
    while (!que.empty()) {
        p cur = que.top();
        que.pop();
        int v = cur.second;
        used[v] = true;
        if (dist[v] < cur.first) continue;
        for (int i = 0; i < g[v].size(); i++) {
            Edge e = g[v][i];
            if (!used[e.to] && dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                que.push(p(dist[e.to], e.to));
            }
        }
    }
}
int main() {
    int n, q, k;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        g[a - 1].push_back((Edge){b - 1, c});
        g[b - 1].push_back((Edge){a - 1, c});
    }
    cin >> q >> k;
    solve(k - 1);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        cout << dist[x - 1] + dist[y - 1] << endl;
    }
    return 0;
}


Measured memory_bytes: 11248
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 9] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    d[a][b] = c
    d[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)


Measured memory_bytes: 46040
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [int(c) for c in S()]
    for i in range(8):
        c = a[0]
        r = [a[0]]
        for j in range(3):
            if i&(2**j):
                c += a[j+1]
                r.append('+')
            else:
                c -= a[j+1]
                r.append('-')
            r.append(a[j+1])
        if c == 7:
            return ''.join(map(str,r)) + '=7'

    return -1



print(main())




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

using namespace std;

int main()
{
	long long n, a[200000], l = -2000000000, r = 2000000000, m1, m2, s1, s2, s3, s4;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> a[i];
		
	for (int i = 0; i < 100; i++)
	{
		m1 = (l*2+r)/3;
		m2 = (l+r*2)/3;
		s1 = s2 = 0;
		
		for (long long j = 0; j < n; j++)
		{
			s1 += abs(a[j]-(m1+j+1));
			s2 += abs(a[j]-(m2+j+1));
		}
		
		if (s1 <= s2)
			r = m2;
		else
			l = m1;
	}
	
	s1 = s2 = s3 = s4 = 0;
	
	for (long long j = 0; j < n; j++)
	{
		s1 += abs(a[j]-(m1+j+1));
		s2 += abs(a[j]-(m2+j+1));
		s3 += abs(a[j]-(l+j+1));
		s4 += abs(a[j]-(r+j+1));
	}
	
	cout << min(min(s1, s2), min(s3, s4));
}

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

int main(){
    int A,B,C,K,max_sum=0;
    cin >> A >> B >> C;
    cin >> K;
    int *ptr = &A;
    if(*ptr < B)ptr = &B;
    if(*ptr < C)ptr = &C;
    *ptr = *ptr << K;
    cout << A+B+C << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
	char c = '\0';

	std::cin >> c;

	switch (c) {
	case 'a':
		std::cout << "vowel";
		break;
	case 'e':
		std::cout << "vowel";
		break;
	case 'i':
		std::cout << "vowel";
		break;
	case 'o':
		std::cout << "vowel";
		break;
	case 'u':
		std::cout << "vowel";
		break;
	default:
		std::cout << "consonant";
		break;
	}

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
 
#define N 1000000

int  judge_char(char);
int  key_data(char *);
void insert(char *); 
int  find(char *);

char str[N][15];

int main(){
 
   int i;
   int n;
   int judge;

   int count=0;
  char order[10];
  char data[15];
  char ans[N][5];
    
  scanf("%d",&n);

  for(i=0;i<n;i++){
  scanf("%s %s",order,data);
  if(strcmp(order,"insert")==0){
  insert(data); 
  }
  else if(strcmp(order,"find")==0){
  judge = find(data);
  if(judge==1){
  strcpy(ans[count],"yes");
  count++;
  }
  else{
  strcpy(ans[count],"no");
  count++;
    }
   }
  }

  for(i=0;i<count;i++){
  printf("%s\n",ans[i]);
  }
  
  return 0;
}


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


int key_data(char *arr){
  
  int i;
  int p=1;
  int data=0;
  
  for(i=0;i<strlen(arr);i++){
    data += p * judge_char(arr[i]);
    p *= 5;
  } 
  return data;
  }

void insert(char *arr){
  int i;
  int h;
  int h1;
  int h2;
  int key;

  key = key_data(arr);
  
  h1 = key % N;
  h2 = 1 + key % (N -1);

  for(i=0;;i++){
  h = ( h1 + i * h2 ) % N;
  if(str[h][0]=='\0'){
    strcpy(str[h],arr);
    break;
  }
  if(strcmp(str[h],arr)==0) break;
 }  
}
int find(char *arr){
  int i;
  int h;
  int h1;
  int h2;
  int key;

  key = key_data(arr);
  
  h1 = key % N;
  h2 = 1 + key % (N -1);

  for(i=0;;i++){
  h = ( h1 + i * h2 ) % N;
  if(strcmp(str[h],arr)==0) return 1;
  if(str[h][0]=='\0') return -1;
  }
}

Measured memory_bytes: 19304
#include<bits/stdc++.h>
using namespace std;
#define N 100000
int main()
{
	long long arr[N],n,i,s=1;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>arr[i];
	long long t=arr[0];
	for(i=1;i<n;i++)
	{
		if(t!=2)
		{
			t=arr[t-1];
			s++;
		}
		else
		{
			cout<<s<<endl;
			break;	
		}
	}
	if(i==n)
		cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")
#define charsize 100005 //10^5+5

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a= c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){n+= n<0?((-n)/MOD1+1)*MOD1:0; return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

int main(void){
    // char ;
    ll n,k,ans=0;
    scanf("%lld%lld",&n,&k);
    // ll [n];
    rep(i,k+1,n+1){
        ans+= (n+1) - ( n/i*k + min2(n%i+1 , k) );
        // printf("%lld\n",ans);
    }
    if(k==0) ans-=n;


    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int f[100005];
int  maxx=-1,n,temp;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&f[i]);
    	if(f[i]>maxx)
		{
			maxx=f[i];
		
		}
	}
	if(n==2)
	{
		cout<<max(f[1],f[2])<<" "<<min(f[1],f[2])<<endl;
		return 0;
	}
		double mm=maxx/2.0;
		double minn=maxx;
	    for(int i=1 ;i<=n;i++)
	    {
	    	if(abs(f[i]-mm)<minn)
	    	{
	    	//	cout<<f[i]<<" "<<minn<<endl;
				minn=abs(f[i]-mm);
	    		temp=f[i];
			}
		}
		cout<<maxx<<" "<<temp;
		    return 0;
}

Measured memory_bytes: 640
#include<bits//stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
ll n,k, y,x, w = 1,ans = 1;
const int MOD = 1000000007;
int main(void) {
	cin >> n >> k;vector<ll> a(n);
	rep(i, n) cin >> a[i];
	sort(ALL(a)); int l = 0,r = n-1;
	if (k % 2) {
		ans = a[r--]; --k;
		if (ans < 0) w = -1;
	}
	while (k) {
		x = a[l] * a[l + 1], y = a[r] * a[r - 1];
		if (x * w > y * w) {
            ans *= (x%MOD); ans %= MOD; l += 2;
		}
		else {
            ans *= (y%MOD); ans %= MOD; r -= 2;
		}k -= 2;
	}cout << (ans+MOD)%MOD << endl;
}

Measured memory_bytes: 4844