akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Globalization;
using System.IO;
using System.Text;
using static Scanner;

class Program
{
    static void Main(string[] args) {
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Solve();
        Console.Out.Flush();
    }
    static void Solve() {
        var N = ScanInt();
        var array = new (int index, string s, int p)[N];
        for (int i = 0; i < N; i++) {
            array[i].index = i;
            array[i].s = Scan();
            array[i].p = ScanInt();
        }
        Array.Sort(array, (a, b) => a.s != b.s ? string.Compare(a.s, b.s, StringComparison.Ordinal) : -a.p.CompareTo(b.p));
        foreach (var (index, _, _) in array) {
            Console.WriteLine(index + 1);
        }
    }
}

public static class Scanner
{
    static readonly Stream stream = Console.OpenStandardInput();
    static readonly byte[] buffer = new byte[1024];
    static int length, p;
    static bool isEof;
    private static byte ConsoleIn() {
        if (isEof) return 0;
        if (p < length) return buffer[p++];
        p = 0;
        if ((length = stream.Read(buffer, 0, 1024)) > 0) return buffer[p++];
        isEof = true;
        return 0;
    }
    public static char GetChar() {
        var by = ConsoleIn();
        while ((by < '!' || '~' < by) && !isEof) by = ConsoleIn();
        return (char) by;
    }
    public static string Scan() {
        var sb = new StringBuilder();
        for (var ch = GetChar(); '!' <= ch && ch <= '~'; ch = (char) ConsoleIn()) {
            sb.Append(ch);
        }
        return sb.ToString();
    }
    public static int ScanInt() {
        var temp = 0;
        for (var ch = GetChar(); '0' <= ch && ch <= '9'; ch = (char) ConsoleIn()) {
            temp = temp * 10 + ch - '0';
        }
        return temp;
    }
}

Measured memory_bytes: 23992
N = int(input())
B = [int(n) for n in input().split()]

A = [0] * N

A[0] = B[0]
A[-1] = B[-1]

for i in range(1, N-1):
    A[i] = B[i-1]

    if A[i] > B[i]:
        A[i] = B[i]
    
print(sum(A))

Measured memory_bytes: 8956
#include<iostream>
using namespace std;
int main(){
int n,k,i,keep[111111],p1=0,p2=0,count=0,ans=0;
char s[111111];
cin>>n>>k>>s;
if(s[0]=='0')
count++;
keep[0]=0;
p1++;
for(i=1;i<n;i++){
if(s[i]=='0'){
if(s[i-1]=='1'){
if(count>=k){
if(i-keep[p2]>ans)
ans=i-keep[p2];
p2++;
}
count++;
}
}
else{
if(s[i-1]=='0'){
keep[p1]=i;
p1++;
}
}
}
if(i-keep[p2]>ans)
ans=i-keep[p2];
if(count<=k)
ans=n;
cout<<ans<<endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<set>

std::set<int> pos[26];

int main() {
  int N, Q;
  std::string S;
  std::cin >> N >> S >> Q;
  for(int i = 0; i < N; ++i) pos[S[i]-'a'].insert(i+1);
  for(int i = 0; i < Q; ++i) {
    int t; std::cin >> t;
    if(t == 1) {
      int k; char c; std::cin >> k >> c;
      for(int i = 0; i < 26; ++i) {
        if(i == c - 'a') pos[i].insert(k);
        else pos[i].erase(k);
      }
    } else {
      int l, r; std::cin >> l >> r;
      int count = 0;
      for(int i = 0; i < 26; ++i) {
        auto it = pos[i].lower_bound(l);
        if(it != pos[i].end() && *it <= r) ++count;
      }
      std::cout << count << std::endl;
    }
  }
  return 0;
}


Measured memory_bytes: 24196
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m = map(int, readline().split())
ks = [list(map(int, readline().split()))[1:] for _ in range(m)]
p = list(map(int, readline().split()))
ans = 0
for bit in product([0, 1], repeat=n):
    for pp, ksi in zip(p, ks):
        cnt = 0
        for j in range(n):
            if bit[j] == 1 and (j + 1) in ksi:
                cnt += 1
        if cnt % 2 != pp:
            break
    else:
        ans += 1

print(ans)


Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
    
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        string[] input = Console.ReadLine().Split(' ');
        ulong[] A = new ulong[N];

        if(N == 1)
        {
            Console.WriteLine(0);
        }
        else
        {
            for(int i=0; i<N; i++) {
                A[i] = Convert.ToUInt64(input[i]);
            }

            ulong sum = 0;

            for(int i=1; i<N; i++) {
                if(A[i] < A[i-1]) {
                    ulong stage = A[i-1] - A[i];
                    sum += stage;
                    A[i] = A[i-1];
                }
            }

            Console.WriteLine(sum);
        }
    }
}

Measured memory_bytes: 46772
N=int(input())
both=0
one_A=0
one_B=0
sum=0
for i in range(N):
    S=list(input())
    if S[0]=='B' and S[len(S)-1]=='A':
        both+=1
    elif S[0]=='B':
        one_B+=1
    elif S[len(S)-1]=='A':
        one_A+=1
    for i in range(1,len(S)-1):
        if  S[i-1]=='A'and S[i]=='B':
            sum+=1
if both>0:
    sum+=(both-1)
    if one_A>0:
        sum+=1
        one_A-=1
    if one_B>0:
        sum+=1
        one_B-=1
    if one_A>one_B:
        sum+=one_B
    else:
        sum+=one_A
else:
    if one_A>one_B:
        sum+=one_B
    else:
        sum+=one_A
print(sum)

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

const int MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to))
#define _sort(a) sort(a.begin(), a.end())
#define _sortd(a) sort(a.rbegin(), a.rend())
#define reverse(s) reverse(s.begin(), s.end())
#define p(s) cout << (s) << endl

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

template<class T>
T max(vector<T> &v) {
  return *max_element(v.begin(), v.end());
}

template<class T>
T min(vector<T> &v) {
  return *min_element(v.begin(), v.end());
}

void py(bool isUpper = false) {
  if (isUpper) {
    p("YES");
  } else {
    p("Yes");
  }
}

void pn(bool isUpper = false) {
  if (isUpper) {
    p("NO");
  } else {
    p("No");
  }
}

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

  if (!(1 <= a && a <= 9) || !(1 <= b && b <= 9)) {
    p("-1");
  } else {
    p(a * b);
  }
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
#define N 300500
#define mod 1000000007
int n,p[N],su[N],v[N],su1[N],as,as1,tr[N],lb[N],tr2[N],rb[N],tr3[N];
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
void add(int x,int k){for(int i=x;i<=n;i+=i&-i)tr[i]=(tr[i]+k)%mod;}
int que(int x){int as=0;for(int i=x;i;i-=i&-i)as=(as+tr[i])%mod;return as;}
void add2(int x,int k){for(int i=x;i<=n;i+=i&-i)tr2[i]+=k;}
int que2(int x){int as=0;for(int i=x;i;i-=i&-i)as+=tr2[i];return as;}
void add3(int x,int k){for(int i=x;i<=n;i+=i&-i)tr3[i]=(tr3[i]+k)%mod;}
int que3(int x){int as=0;for(int i=x;i;i-=i&-i)as=(as+tr3[i])%mod;return as;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]),su[p[i]]++;
	for(int i=n-1;i>=1;i--)su[i]=su[i+1]+su[i]-1;
	as=1;
	for(int i=1;i<=n;i++)as=1ll*as*su[i]%mod;
	if(!as){printf("0\n");return 0;}
	lb[0]=1;
	for(int i=1;i<=n;i++)
	{
		v[i]=1ll*(su[i]-1)*pw(su[i],mod-2)%mod;
		su1[i]=v[i];if(su1[i-1])su1[i]=1ll*su1[i]*su1[i-1]%mod;
	}
	for(int i=n;i>=1;i--)if(v[i+1])rb[i]=rb[i+1];else rb[i]=i;
	for(int i=1;i<=n;i++)if(v[i-1])lb[i]=lb[i-1];else lb[i]=i;
	for(int i=1;i<=n;i++)
	{
		int su11=que(p[i])-que(lb[p[i]]-1),su2=que2(p[i])-que2(lb[p[i]]-1);
		as1=(as1+1ll*as*su11%mod*su1[p[i]]%mod*(mod+1)/2)%mod;
		su11=que3(rb[p[i]])-que3(p[i]),su2=que2(n)-que2(p[i]);
		as1=(as1+1ll*as*su2%mod-1ll*as*su11%mod*pw(su1[p[i]],mod-2)%mod*(mod+1)/2%mod)%mod;
		add(p[i],pw(su1[p[i]]?su1[p[i]]:1,mod-2)),add2(p[i],1);add3(p[i],su1[p[i]]);
	}
	printf("%d\n",(as1+mod)%mod);
}

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

int main(){

	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif

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

	long long n; cin >> n;

	long long money = 1000;
	long long stocks = 0;	
	int a[n+1];
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	a[n] = 0;
	long long high = 1000;
	int prec = 2000;
	for(int i=0;i<n;i++){
		if(a[i]<prec){
			long long temp = money/a[i];
			money = money % a[i];
			stocks += temp;
		}
		if(a[i]>a[i+1]){
			money += a[i]*stocks;
			stocks = 0;
		}
		if(money>high) high = money;
//		cout << money << endl;
	}
	cout << high << endl;
	return 0;
}

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

#define mod 1000000007

int main() {
    int N;
    cin >> N;
    vector<ll>A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<ll>pow2(63, 1);
    for (int i = 1; i < 63; ++i) {
        pow2[i] = pow2[i-1] * 2 % mod;
    }

    vector<int>cnt(63, 0);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 63; ++j) {
            int k = A[i] % 2;
            A[i] /= 2;
            if(k == 0) {
                ans += cnt[j] * pow2[j];
            } else{
                ans += (i - cnt[j]) * pow2[j];
            }
            ans %= mod;
            cnt[j] += k;
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 2560
def main():
    MOD = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    a_sum = sum(a)
    ans = 0
    
    for i in range(n):
        ans += a[i] * (a_sum - a[i])
    print(ans // 2 % MOD)
        
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 31408
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Text;

namespace AtCoder.ABC
{
	class QuestionB
	{
		public static void Main(string[] args)
		{
            var scanner = new Scanner();

            var s = scanner.next();

            var sum = 0L;
            for(int i = 0; i< s.Length; i++) {
                sum += s[i] - '0';
			}

            Console.WriteLine(sum % 9 == 0 ? "Yes" : "No");
		}

        class Scanner
        {
            string[] s;
            int i;

            char[] cs = new char[] { ' ' };

            public Scanner()
            {
                s = new string[0];
                i = 0;
            }

            public string next()
            {
                if (i < s.Length) return s[i++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();
                s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
                if (s.Length == 0) return next();
                i = 0;
                return s[i++];
            }

            public int nextInt()
            {
                return int.Parse(next());
            }
            public int[] ArrayInt(int N, int add = 0)
            {
                int[] Array = new int[N];
                for (int i = 0; i < N; i++) {
                    Array[i] = nextInt() + add;
                }
                return Array;
            }

            public long nextLong()
            {
                return long.Parse(next());
            }

            public long[] ArrayLong(int N, long add = 0)
            {
                long[] Array = new long[N];
                for (int i = 0; i < N; i++) {
                    Array[i] = nextLong() + add;
                }
                return Array;
            }

            public double nextDouble()
            {
                return double.Parse(next());
            }


            public double[] ArrayDouble(int N, double add = 0)
            {
                double[] Array = new double[N];
                for (int i = 0; i < N; i++) {
                    Array[i] = nextDouble() + add;
                }
                return Array;
            }
        }
    }
}


Measured memory_bytes: 26588
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  while (true) {
    int n; cin >> n;
    if (!n) break;
    V<string> s(n); for (auto&& e : s) cin >> e;
    reverse(begin(s), end(s));
    V< pair<int, int> > v;
    for (const auto& e : s) {
      if (isdigit(e.back())) {
        v.emplace_back(e.back() - '0', e.size());
      } else {
        if (e.back() == '+') {
          int s = 0;
          while (!v.empty() and v.back().second > (int)e.size()) {
            s += v.back().first;
            v.pop_back();
          }
          v.emplace_back(s, e.size());
        } else {
          int s = 1;
          while (!v.empty() and v.back().second > (int)e.size()) {
            s *= v.back().first;
            v.pop_back();
          }
          v.emplace_back(s, e.size());
        }
      }
    }
    cout << v.back().first << '\n';
  }
}


Measured memory_bytes: 3212
# -*- coding: utf-8 -*-

"""
参考：https://misteer.hatenablog.com/entry/ABC113
・DPとビット全検索
"""

H, W, K = map(int, input().split())
# 0-indexed
K -= 1
MOD = 10 ** 9 + 7

dp = [[0] * W for i in range(H+1)]
# 縦棒の長さ0(つまり横棒なし)、一番左の棒を下りてくる1つ
dp[0][0] = 1

for h in range(1, H+1):
    # 縦棒間の数でビット全検索
    for b in range(1 << (W-1)):
        # 横棒が隣接していないチェック
        s = format(b, 'b')
        if s.count('11'):
            continue
        # ある始点の今回の移動先を保持する
        perm = [0] * W
        for i in range(W):
            perm[i] = i
        # 各縦棒間に横棒があるかループ
        for i in range(W-1):
            # あるビットが立っているかどうかで判別
            # (あみだが左始まりだから、ビットも左から始まってると思った方がイメージしやすいかも。
            # それかあみだが右から始まってると思うか。)
            if b >> i & 1:
                # 横棒があればひとつ先とスワップ
                perm[i], perm[i+1] = perm[i+1], perm[i]
        for i in range(W):
            # 前回のW-1ビット分を今回のW-1ビット分の回数足し合わせてくから、最終的に膨大になる
            dp[h][perm[i]] += dp[h-1][i]
            dp[h][perm[i]] %= MOD

print(dp[H][K])


Measured memory_bytes: 3064
#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 FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define IN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////

//AtCoder Beginner Contest 101

ll sumDigit(ll x){
	ll ret = 0;
	while(true){
		if (x == 0) return ret;
		ret = ret + (x % 10);
		x = x / 10;
	}
}


int main(){
	int N,K; SCD2(N,K);
	static int A[100002];
	int onein;
	
	FORq(i,1,N){
		int x;SCD(x);
		if (x==1) onein = i;
	}
	
/* 	int req1,req2;
	req1 = onein - 1;
	req2 = N - onein;
	
	int ans1,ans2;
	K--;
	if (req1 % K == 0) {
		ans1 = req1/ K;
	}else{
		ans1 = (req1 / K)+1;
	}
	
	if (req2 % K == 0) {
		ans2 = req2/ K;
	}else{
		ans2 = (req2 / K)+1;
	}
	 */
	 
	if (N==K){
		PRINTD(1);
		return 0;
	}
	
	int ans = 0;
	ans++;
	N = N-K;
	K--;
	if (N % K == 0) {
		ans += N/ K;
	}else{
		ans += (N / K) +1;
	}
	
	PRINTD(ans);
	
	return 0;
}

Measured memory_bytes: 256
import numpy as np
n,t = map(int, input().split())
DP = np.full((t), -float("inf"))
DP[0] = 0
ans = 0
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
for a,b in ab:
    ans = max(ans, max(DP)+b)
    if a<t:
        DP[a:] = np.maximum(DP[a:], DP[:-a]+b)

ans = int(ans)
print(ans)

Measured memory_bytes: 14792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
struct edge{int from;int to;ll cost;};
int main(){
    int n,m;cin >> n >> m;
    vector<edge> g(m);
    vector<ll> d(n,INF);
    for(int i=0;i<m;i++){
        int a,b;ll c;
        cin >> a >> b >> c;
        a--,b--;
        g[i]=(edge{a,b,-c});
    }
    d[0]=0;
    for(int i=0;i<2*n;i++){
        for(int j=0;j<m;j++){
            if(d[g[j].from]!=INF&&d[g[j].to]>d[g[j].from]+g[j].cost){
                d[g[j].to]=d[g[j].from]+g[j].cost;
                if(i>=n-1&&g[j].to==n-1){
                    cout << "inf" << endl;
                    return 0;
                }
            }
        }
    }
    cout << -d[n-1] << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		final int n = sc.nextInt();

		List<Integer> list = new ArrayList<Integer>();

		for (int i = 0; i < n; i++) {
			list.add(sc.nextInt());
		}

		Collections.sort(list);
		Collections.reverse(list);

		int alicePoint = 0;
		int bobPoint = 0;
		for (int j = 0; j < n; j++) {
			if ((j + 1) % 2 != 0) {
				alicePoint = alicePoint + list.get(j);
			} else {
				bobPoint = bobPoint + list.get(j);
			}
		}

		System.out.println(alicePoint - bobPoint);

	}

}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define w(x) scanf("%d",&x);while(x--)
#define ws(x) scanf("%d",&x);getchar();while(x--)
#define rep(i,b) for(i=0;i<=b;i++)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 2*acos(0.0)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const int N=1e6+2;
long long  mod=1e9+9;
int t,j,cs=0,n,a,b,i;
string s;

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



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

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

	int a = S / 100;
	int b = S - a*100;

	bool a_mm = false;
	bool b_mm = false;
	if (1 <= a && a <= 12) {
		a_mm = true;
	}
	if (1 <= b && b <= 12) {
		b_mm = true;
	}



	if (a_mm && b_mm) {
		cout << "AMBIGUOUS" << endl;
		return 0;
	}
	else if (a_mm && (!b_mm)) {
		cout << "MMYY" << endl;
		return 0;
	}
	else if (b_mm && (!a_mm)) {
		cout << "YYMM" << endl;
		return 0;
	}
	else if ((!a_mm) && (!b_mm)) {
		cout << "NA" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = Integer.parseInt(sc.nextLine());
			
			if(n == 0){
				break;
			}
			
			int[][] adj = new int[10][10];
			for(int i = 0; i < 10; i++){
				for(int j = 0; j < 10; j++){
					adj[i][j] = -1;
				}
			}
			
			
			int town_max = 0;
			for(int i = 0; i < n; i++){
				String[] strs = sc.nextLine().split(" ");
				int start = Integer.parseInt(strs[0]);
				int end = Integer.parseInt(strs[1]);
				int cost = Integer.parseInt(strs[2]);
				
				if(town_max < start){
					town_max = start;
				}else if(town_max < end){
					town_max = end;
				}
				
				adj[start][end] = adj[end][start] = cost;
			}
			
			int min_num = 0;
			int min_cost = Integer.MAX_VALUE;
			
			for(int i = 0; i <= town_max; i++){
				int c = digstra(i, adj, town_max + 1);
				if(c < min_cost){
					min_num = i;
					min_cost = c;
				}
			}
			
			
			System.out.println(min_num + " " + min_cost);
		}
		
	}
	
	public static int digstra(int start,int[][] adj, int nodes){
		int[] costs = new int[nodes];
		for(int i = 0; i < nodes; i++){
			if(i == start){
				costs[i] = 0;
			}else{
				costs[i] = Integer.MAX_VALUE;
			}
		}
		
		HashSet<Integer> arrived = new HashSet<Integer>(nodes);
		HashSet<Integer> unreached = new HashSet<Integer>(nodes);
		
		for(int i = 0; i < nodes; i++){
			unreached.add(i);
		}
		
		while(!unreached.isEmpty()){
			int min_cost = Integer.MAX_VALUE;
			int min_node = -1;
			
//			for(int i = 0; i < nodes; i++){
//				System.out.print("[" + i + "] = " + costs[i] + ", ");
//			}
//			System.out.println();
			
			for(Iterator<Integer> ite = unreached.iterator(); ite.hasNext();){
				int node = ite.next();
				
				if(costs[node] < min_cost){
					min_cost = costs[node];
					min_node = node;
				}
			}
			
			unreached.remove(min_node);
			arrived.add(min_node);
			
			for(int i = 0; i < nodes; i++){
				if(adj[min_node][i] != -1){
					if((min_cost + adj[min_node][i]) < costs[i]){
						costs[i] = min_cost + adj[min_node][i];
					}
				}
			}
		}
		
		int sum = 0;
		for(int i = 0; i < nodes; i++){
			sum += costs[i];
		}
		
		return sum;
	}
	
}

Measured memory_bytes: 12000
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print((n-(n>>1))/n)
    return

#B
def B():
    n,k = LI()
    h = LI()
    ans = 0
    for i in h:
        if i >= k:
            ans += 1
    print(ans)
    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()


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

int main() {
   ll i,j,k;
    string s;
    cin >> s;
  
  if(s[0]=='S')
  {
    if(s[1]=='U')
    {
  cout << 7 << endl;
    }
    else
    {
        cout << 1 << endl;
    }
  }
   if(s[0]=='M')
  {
    
        cout << 6 << endl;
  
  }
   if(s[0]=='T')
  {
    if(s[1]=='U')
    {
  cout << 5 << endl;
    }
    else
    {
        cout << 3 << endl;
    }
  }

   if(s[0]=='W')
  {
       cout << 4 << endl;
    
  }
   if(s[0]=='F')
  {
   
        cout << 2 << endl;
    
  }

}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    long MOD = (long)1e9 + 7;

    void run() {
        Scanner sc = new Scanner(System.in);

        long L = sc.nextLong(), R = sc.nextLong();
        System.out.println(count(L, R));
    }

    long dev(long L, long R) {

        long cnt = 0;
        for (long x = L; x <= R; x++) for (long y = x; y <= R; y++) {
            if ((y % x) == (x ^ y)) cnt++;
        }
        return cnt;
    }

    int DIGIT = 60;
    long count(long L, long R) {
        String l = Long.toBinaryString(L);
        String r = Long.toBinaryString(R);

        for (int i = l.length(); i <= DIGIT; i++) l = "0" + l;
        for (int i = r.length(); i <= DIGIT; i++) r = "0" + r;
        long[][][][] dp = new long[DIGIT + 1][2][2][2]; // i番目まで見て、確実にL以上かどうか 、確実にR以下かどうか、ビットを立てているかどうか

        dp[0][0][0][0] = 1;
        for (int i = 1; i <= DIGIT; i++) {
            int ln = 1 - l.charAt(i) + '0', rn = r.charAt(i) - '0';

            for (int X = 0; X < 2; X++) for (int Y = 0; Y < 2; Y++) for (int Z = 0; Z < 2; Z++) {
                // x: 1, y: 1
                if ((Y | rn) == 1)
                    dp[i][X | ln][Y][1] += dp[i - 1][X][Y][Z];
                // x: 0, y: 0
                if ((X | ln) == 1)
                    dp[i][X][Y | rn][Z] += dp[i - 1][X][Y][Z];
                // x: 0, y: 1
                if (((Y | rn) == 1) && ((X | ln) == 1) && Z == 1)
                    dp[i][X][Y][Z] += dp[i - 1][X][Y][Z];
                dp[i][X | ln][Y][1] %= MOD;
                dp[i][X][Y][Z] %= MOD;
                dp[i][X][Y | rn][Z] %= MOD;
            }
        }
        long ans = 0;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
            ans += dp[DIGIT][i][j][1];
        }
        return ans % MOD;
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }

}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
/*#include <ctime>
#include <list>
#include <numeric>
#include <bitset>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <utility>
#include <fstream>
#include <sstream>
#include <cmath>
#include <stack>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <iomanip>
#include <limits>*/

using namespace std;


/// Bismilahir Rahmanir Rahim


typedef unsigned int ui;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef short int si;
typedef unsigned short int usi;
typedef pair <int, int> pii;


#define CASE false
#define TEST false
#define BUFFER true
#define TIME false
#define DEBUG true
#define SET_GEN false
#define File false
#define _ << " " <<
#define __ << "\n"
#define ff first
#define ss second
#define EMPTY_VAL -1
#define RANGE(a, b) (rand() % (b-a+1) + a)


const double pi = acos(-1.);
const double eps = 1e-8;
const int inf = 2147483647;
const int _inf = -2147483648;
const lli INF = 1e18;
const int mod = 1e9+7;
const int maxn = 201;

void delay(int sec); // DEBUG


void solution(void)
{
    int x, y;
    int a, b;

    cin >> x >> y;

    b = y-2*x;
    if (b < 0 || b % 2) cout << "No\n";
    else if (x-(b/2) >= 0) cout << "Yes\n";
    else cout << "No\n";



    return ;
}

int main(int argc, char *arv[])
{
    #if File
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    #if BUFFER
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #endif

    #if SET_GEN
    srand((unsigned int) time(0));
    #endif

    int t = 1;

    #if CASE
    int cnt = 1;
    #endif

    #if TEST
    cin >> t;
    #endif

    #if TIME
    clock_t start_time, end_time;
    double time_elapsed;
    #endif


    while(t--) {

        #if TIME
        start_time = clock();
        #endif

        #if CASE
        cout << "Case #" << cnt++ << ": ";
        #endif

        solution();

        #if TIME
        end_time = clock();

        time_elapsed = (double) (end_time - start_time) / CLOCKS_PER_SEC;

        cout << "\nRuntime: " << fixed << setprecision(7) << time_elapsed << "\n";
        #endif
    }


    return 0;
}

void delay(int sec)
{
    int mili_sec = 1000 * sec;

    clock_t start_time = clock();

    while (clock() < start_time + mili_sec);

    return ;
}
/*
1
6 5
1 2 3
1 5 2
5 4 1
2 3 4
3 6 5
5
6 5
*/


Measured memory_bytes: 3580
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
#define INF (1<<29)

int main(){
  int n, a[100010];
  cin >> n;
  for(int i=0;i<=n;i++)a[i]=i;
  for(int i=2;i<=n;i++){
    int x=6, y=9;
    while(x<=i){
      a[i]=min(a[i],a[i-x]+1);
      x=x*6;
    }
    while(y<=i){
      a[i]=min(a[i],a[i-y]+1);
      y=y*9;
    }
  }
  cout << a[n] << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define mm(x,n) memset(x,n,sizeof(x))
#define IOS cin.tie(0); ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxn = 2e5+5;

int main(){
	ll n,m,ans = 0;
	cin >> n >> m;
	while(n <= m){
		n += n;
		ans++;
	} 
	cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  long long k;
  cin>>k;
  long long a = 0;
  char p;
  for(int i = 0;i<s.size();i++){
    if(s.at(i) == '1'){
      a++;
    }
    else{
      p = s.at(i);
      break;
    }
  }
  if(a<k){
    cout << p << endl;
  }
  else{
    cout << 1 << endl;
  }
  return 0;
}

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

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

  int ans;
  for (int i = 2; i < s.size(); i += 2) {
    string x, y;
    for (int j = 0; j < (s.size() - i) / 2; j ++) {
      x += s.at(j);
    }
    for (int j = (s.size() - i) / 2; j < s.size() - i; j ++) {
      y += s.at(j);
    }
    if (x == y) {
      ans = s.size() - i;
      break;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
import math

a,b = map(int,input().split())

c = math.ceil
min8, max8 = c(a*12.5), c((a+1)*12.5)
min10, max10 = c(b*10), c((b+1)*10)

l8, l10 = list(range(min8, max8)), list(range(min10, max10))
s8, s10 = set(l8), set(l10)

ss = s8 & s10
#print(min8, max8, min10, max10)
print(min(ss) if len(ss) >0 else -1)
#print(238*0.08)

Measured memory_bytes: 9204
//love yjl forever
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int INF=0x3f3f3f3f,N=3000+5,mo=998244353;
int n,S;
ll dp[N];
ll a[N];
ll ksm(int x,int y)
{
	if(y==0) return 1;
	
	ll tmp=ksm(x,y/2);
	if(y&1)
	{
		return (tmp*tmp*x)%mo;
	}
	else 
	{
		return (tmp*tmp)%mo;
	}
}
int main()
{
/*	freopen("","r",stdin);
	freopen("","w",stdout);*/
	int i,j;
	cin>>n>>S;
	ll ny=ksm(2,mo-2);
	
	for(i=1;i<=n;i++)
		cin>>a[i];
		
	dp[0]=ksm(2,n);
	
//	cout<<dp[0]<<endl;
	for(i=1;i<=n;i++)
	{
		for(j=S;j>0;j--)
		{
			if(j-a[i]<0) continue;
			dp[j]=(dp[j]+dp[j-a[i]]*ny)%mo;
		}
	}
	
//	for(i=1;i<=S;i++)
//		cout<<dp[i]<<" ";
//		
//	cout<<endl;
	
	cout<<dp[S]<<endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

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

int main()
{
    int n, m;
    cin >> n >> m;
    map<int, ll> card;
    set<ll> ca;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        ca.insert(a);
        card[a]++;
    }
    for(int i = 0; i< m; i++){
        int b, c;
        cin >> b >> c;
        card[c] += b;
        ca.insert(c);
    }
    ll ans = 0;
    ll num = n;

    // for(auto val: ca){
    //     cout << val << endl;
    // }

    for(auto itr = ca.end(); itr != ca.begin(); itr--){
        if(itr == ca.end()) itr--;
        ll tmp = *itr;
        //cout << "tmp: " << tmp << endl;
        if(num >= card[tmp]){
            num -= card[tmp];
            ans += tmp*card[tmp];
            //cout << "ans1: " << ans << endl;
        }else{
            ans += tmp*num;
            num = 0;
            break;
        }
    }
    if(num != 0) ans += num * (*ca.begin());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 25480
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n,m;
    cin >> n >> m;
    vector<vector<ll>> g(n);
    for(int i=0;i<m;i++){
        ll a,b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<ll> ans(n,-1);
    queue<ll> que;
    que.push(0);

    while(!que.empty()){
        int cur = que.front();
        que.pop();
        for(int i=0;i<g[cur].size();i++){
            if(ans[g[cur][i]] == -1){
                ans[g[cur][i]] = cur + 1;
                que.push(g[cur][i]);
            }
        }
    }


    for(int i=1;i<n;i++){
        if(ans[i] == -1){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    for(int i=1;i<n;i++){
        cout << ans[i] << endl;
    }

    return 0;
}



Measured memory_bytes: 12904
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    int n,m,k; std::cin >> n >> m;
    std::vector<int> tabemono(m+1,0);
    rep(i,n){
        std::cin >> k;
        int aij;
        rep(j,k){
            std::cin >> aij;
            tabemono[aij]++;
        }
    }

    int ans = 0;
    rep(i,m+1){
        if(tabemono[i]==n) ans++;
    }

    std::cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3608
#include<cstdio>
#include<algorithm>
using namespace std;
int x[100000],a,n,q;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&x[i]);
	scanf("%d",&q);x[n]=1<<30;int cnt=0;
	for(int i=0;i<q;i++){
		scanf("%d",&a);
		int pos=lower_bound(x,x+n,a)-x;
		if(x[pos]==a)cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 3104
#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 REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1e9+7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

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

template<class T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
///////////////////////////////////////////////
/*⁽⁽(ી₍₍⁽⁽(ી( ˆεˆ )ʃ)₎₎⁾⁾ʃ)₎₎*/
int main(){
	int N,D;
	cin >> N >> D;
	set<int> S;
	FORq(i,1,1000){
		S.insert(i * i);
	}

	static ll X[12][12] = {};
	FORq(i,1,N){
		FORq(j,1,D){
			cin >> X[i][j];
		}
	}

	int ans = 0;

	FORq(i,1,N){
		FORq(j,1,N){
			if (i >= j) continue;
			ll sum = 0;
			FORq(k,1,D){
				sum += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
			}

			if (SIN(sum,S)) ans++;
		}
	}

	cout << ans << "\n";
	return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    string s;
    cin >> s;
    cout << s.substr(0,3) << endl;

    return 0;
}

Measured memory_bytes: 3620
n, k = [int(_) for _ in input().split()]
l = [0] * n
for i in range(k):
    d = int(input())
    a = [int(_) for _ in input().split()]
    for i in range(d):
        l[a[i] - 1] = 1
c = 0
for i in range(n):
    if l[i] == 0:
        c += 1
print(c)

Measured memory_bytes: 67672
from operator import itemgetter
N = int(input())
A = []
B = []
for i in range(N):
  a,b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

A.sort()
B.sort()

if N % 2 > 0:
  print(abs(B[(N-1) // 2] - A[(N-1) // 2]) + 1)
else:
  B1,B2 = B[N//2-1], B[N//2]
  A1,A2 = A[N//2-1], A[N//2]
  xb, xa = (B1+B2)/2, (A1+A2)/2
  print(int((xb-xa) * 2) + 1)



Measured memory_bytes: 25620
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n, p, rp; cin >> n >> p; rp = p;
  map<long long, long long> q;
  for(long long i = 2; i*i <= p; i++){
    auto doIt = [&](long long x){
      while(p % x == 0) q[x]++, p /= x;
    };
    doIt(i);
  }
  if(p != 1) q[p]++;
  long long ans = 1;
  for(auto it : q){
    long long g = it.second / n;
    for(long long j = 0; j < g; j++)
      ans *= it.first;
  }
  cout << ans << endl;
  return 0;
}


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

const int MAX_N = 44;

int main() {
    vector<int> fib(MAX_N + 1);
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i <= MAX_N; i++) fib[i] = fib[i - 1] + fib[i - 2];
    int N; cin >> N;
    cout << fib[N] << endl;
}

Measured memory_bytes: 1196
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC170_b solver = new ABC170_b();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC170_b {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int X = in.nextInt();
            int Y = in.nextInt();
            if ((Y % 2) == 0) {
                if (Y / 2 == X) {
                    out.println("Yes");
                    return;
                }
                int four = 0;
                for (int i = 1; i <= X; i++) {
                    four = i * 4;
                    if (((Y - four) / 2) == (X - i)) {
                        out.println("Yes");
                        return;
                    }
                }
                out.println("No");
            } else {
                out.println("No");
            }


        }

    }
}



Measured memory_bytes: 35892
from heapq import heappush, heappop
from operator import itemgetter

# 入力
N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
c = list(map(int, input().split()))

# 頂点1を根とみなす。
# 頂点1から遠い頂点から順に小さい整数を書き込む
INF = 10**10
G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
x = sorted(c)
ans = '{}\n{}'.format(
    sum(x[:-1]),
    ' '.join(
        str(d)
        for (_, _), d in sorted(
            zip(
                sorted(
                    enumerate(dp[1:]),
                    key=itemgetter(1),
                    reverse=True
                ),
                x
            )
        )
    )
)

# 出力
print(ans)


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int64_t rs64() {
	int64_t n;
	scanf("%" SCNd64, &n);
	return n;
}


#define INF (10000000000LL)
int main() {
	int n = ri(), m = ri();
	std::vector<std::pair<int, int64_t> > hen[n];
	for (int i = 0; i < m; i++) {
		int x = ri();
		int y = ri();
		int cost = ri();
		hen[x].push_back({y, cost});
	}
	
	auto bf = [&] (int start) {
		std::vector<int64_t> dist(n, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				for (auto k : hen[j]) if (dist[k.first] > dist[j] + k.second) {
					if (i == n - 1) return std::vector<int64_t>();
					dist[k.first] = dist[j] + k.second;
				}
		}
		return dist;
	};
	auto solve = [&] () {
		std::vector<std::vector<int64_t> > res(n, std::vector<int64_t>(n, INF));
		auto pot = bf(0);
		if (!pot.size()) return std::vector<std::vector<int64_t> >();
		for (int i = 0; i < n; i++) for (auto &j : hen[i]) j.second += pot[i] - pot[j.first];
		for (int i = 0; i < n; i++) {
			using T = std::pair<int64_t, int>;
			std::priority_queue<T, std::vector<T>, std::greater<T> > que;
			que.push({res[i][i] = 0, i});
			while (que.size()) {
				auto cur = que.top();
				que.pop();
				if (cur.first != res[i][cur.second]) continue;
				for (auto j : hen[cur.second]) {
					if (res[i][j.first] > cur.first + j.second) {
						res[i][j.first] = cur.first + j.second;
						que.push({res[i][j.first], j.first});
					}
				}
			}
			for (int j = 0; j < n; j++) {
				res[i][j] -= pot[i] - pot[j];
				if (res[i][j] > INF / 2) res[i][j] = INF;
			}
		}
		return res;
	};
	auto cor = solve();
	
	if (!cor.size()) {
		std::cout << "NEGATIVE CYCLE" << std::endl;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j) printf(" ");
			if (cor[i][j] == INF) printf("INF");
			else printf("%lld", (long long) cor[i][j]);
		}
		puts("");
	}
	
	return 0;
}



Measured memory_bytes: 3376
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <iomanip>
#include <fstream>
#include <array>
using namespace std;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef pair<int,int> PII;
typedef long long int64;
typedef vector<int> VI;

int n;
string ss[50];
int c[50];

struct state {
	int i, t, k;
	int64 f;
};
bool operator<(const state &s1, const state &s2) {
	return s1.f>s2.f;
}

priority_queue<state> q;
int64 f[50][2][21];

void update(int i, int t, int k, int64 val) {
	if (val!=-1) {
		if (f[i][t][k]==-1 || val<f[i][t][k]) {
			f[i][t][k]=val;
			q.push({i,t,k,val});
		}
	}
}

int main() {
	//freopen("test.in","r",stdin);
	cin >> n;
	REP (i,n) cin >> ss[i] >> c[i];
	INIT(f,-1);
	REP (i,n) {
		update(i,0,ss[i].size(),c[i]);
	}
	while (!q.empty()) {
		state st=q.top(); q.pop();
		int i=st.i, t=st.t, k=st.k;
		if (st.f!=f[i][t][k]) continue;
		// is palindrome
		int is=1;
		int mi=ss[i].size();
		if (t==0) {
			REP (x,k) if (ss[i][mi-k+x]!=ss[i][mi-1-x]) is=0;
		} else {
			REP (x,k) if (ss[i][k-1-x]!=ss[i][x]) is=0;
		}
		if (is) {
			cout << st.f << endl;
			return 0;
		}
		if (t==0) {
			REP (j,n) {
				int mj=ss[j].size();
				int match=1;
				REP (x,min(mj,k)) if (ss[i][mi-k+x]!=ss[j][mj-1-x]) match=0;
				if (match) {
					if (mj<=k) update(i,0,k-mj,st.f+c[j]);
					else update(j,1,mj-k,st.f+c[j]);
				}
			}
		} else {
			REP (j,n) {
				int mj=ss[j].size();
				int match=1;
				REP (x,min(mj,k)) if (ss[i][k-1-x]!=ss[j][x]) match=0;
				if (match) {
					if (mj<=k) update(i,1,k-mj,st.f+c[j]);
					else update(j,0,mj-k,st.f+c[j]);
				}
			}
		}
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl
#define dbgv(x) cout<<#x<<endl;reps(y,x){cout<<y<<" ";}cout<<endl

int main(){
  ll n,k;cin>>n>>k;
  vector<ll> x(n);
  rep(i,n){
    cin>>x[i];
  }
  vector<ll> xright(n);
  vector<ll> xleft(n);
  rep(i,k){
    xright[i]=INF;
    xleft[i]=INF;
  }
  int index_right=0;
  int index_left=0;
  rep(i,n){
    if(x[i]>=0){
      xright[index_right]=x[i];
      index_right++;
    }
    if(x[n-1-i]<0){
      xleft[index_left]=-x[n-1-i];
      index_left++;
    }
  }

  ll ans=INF;
  ans=min(ans,min(xleft[k-1],xright[k-1]));
  
  rep(i,k-1){
    ans= min(ans,2*xleft[i]+xright[k-2-i]);
    ans= min(ans,xleft[i]+2*xright[k-2-i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2688
//#include<bits/stdc++.h>
#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long ll; 
#define PT pair<int, int>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int N, M, R;
int E[201][201];
int D[8][201];
int r[8];
int kotae;

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	N = getint();
	M = getint();
	R = getint();
	rep(i, R) r[i] = getint();

	rep1(i, N) {
		rep1(j, N) E[i][j] = 1e9;
		E[i][i] = 0;
	}
	rep(i, M) {
		int a = getint(), b = getint(), c = getint();
		E[a][b] = c;
		E[b][a] = c;
	}

	rep(i, R) rep1(j, N) D[i][j] = 1e9;
	rep(i, R) D[i][r[i]] = 0;

	priority_queue<PT, vector<PT>, greater<PT>> que;

	rep(k, R) {
		que.push(mp(0, r[k]));
		while (que.size()) {
			PT p = que.top();
			que.pop();
			int i = p.second;
			if (D[k][i] != p.first) continue;
			rep1(j, N) {
				ll d = D[k][i] + E[i][j];
				if (D[k][j] > d) {
					D[k][j] = d;
					que.push(mp(d, j));
				}
			}
		}
	}

	kotae = 1e9;
	int p[8];
	rep(i, R) p[i] = i;
	int saigo = 1;
	rep1(i, R) saigo *= i;
	rep(i, saigo) {
		int kari = 0;
		rep(j, R - 1) {
			kari += D[p[j]][r[p[j + 1]]];
		}
		kotae = min(kotae, kari);
		next_permutation(p, p + R);
	}

	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 512