akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i<n;++i)
using ll = long long;
using P = pair<int,int>;

int main(){
  int a,b;
  cin >> a >> b;
  cout << max(max(a+b,a-b),a*b) << endl;
  return 0;
}


Measured memory_bytes: 256
//c
#include <stdio.h>
#include <string.h>
int main ()
{
	char key[15];
	scanf ("%s", key);
	
	int a = strlen(key);
	int p=1;
	
	for (int  i = 0; i<a; i++ )
	{
	 int p=1;
		if (key[i] == 'B')
		{
			key[i] = 'x';
			
			if (key[i-1] != 'x')
			{
				key[i-1] = 'x';
			}
			
			else if (key[i-1] == 'x')
			{
				while (key [i-p] != '0' && key [i-p] != '1' )
				{
					p++;
				}
				key[i-p]= 'x';
			}
			
		}
	}
	
	for (int j=0; j<a; j++)
	{
		if (key[j] == 'x')
		{
			continue;
		}
		else
		{
			printf("%c", key[j]);
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 1588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp69 {
    class Program {
        static void Main(string[] args) {
            var st = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int A = st[0];
            int B = st[1];
            int C = st[2];
            int D = st[3];

            int ans = 0;

            if (B <= C || D <= A) {
                ans = 0;
            } else {
                ans = Math.Min(B, D) - Math.Max(A, C);
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
def main():
    n, *i = map(int, open(0).read().split())
    a = i[:n]
    _ = i[n]
    s = sum(a)

    m = [0] * (10 ** 5 + 1)
    for x in a:
        m[x] += 1

    ans = []
    for b, c in zip(*[iter(i[n + 1:])] * 2):
        m[c] += m[b]
        s += (c - b) * m[b]
        m[b] = 0
        ans.append(s)

    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


Measured memory_bytes: 43864
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

template<unsigned long long M, unsigned long long B>
struct BasicRollingHash {
  using Uint = unsigned long long;
  using U128 = __uint128_t;
  vector<Uint> hashes, pows;

  template<class T>
  BasicRollingHash(const T& s) { init(s); }

  template<class T>
  void init(const T& s) {
    size_t n = s.size();
    hashes.assign(n + 1, 0);
    pows.assign(n + 1, 0);
    pows[0] = 1;
    for (size_t i = 1; i <= n; ++i) {
      hashes[i] = U128(hashes[i - 1] + s[i - 1]) * B % M;
      pows[i] = U128(pows[i - 1]) * B % M;
    }
  }
  
  template<class T>
  static Uint hash_once(const T& s) {
    Uint h = 0;
    for (size_t i = 1; i <= s.size(); ++i) {
      h = U128(h + s[i - 1]) * B % M;
    }
    return h;
  }

  // [l, r)
  Uint hash(size_t l, size_t r) const {
    r = min(r, size());
    U128 h = M + U128(hashes[r]) - U128(pows[r - l]) * hashes[l] % M;
    if (h > M) h -= M;
    return h;
  }

  size_t size() const {
    return hashes.size() - 1;
  }

  template<class T>
  vector<size_t> search_all(const T& s, size_t l = 0, size_t r = 1 << 30) 
  const {
    auto h = hash_once(s);
    int n = s.size();
    vector<size_t> res;
    for (int i = l; i <= int(min(r, size() - n)); ++i) {
      if (hash(i, i + n) == h) res.push_back(i);
    }
    return res;
  }
};
using RollingHash = BasicRollingHash<(1ull << 61) - 1, 263>;

int main() {
  string s, t;
  cin >> s >> t;
  while (s.size() < t.size()) {
    s += s;
  }
  i64 n = s.size();
  s = s + s + s + s;
  auto ms = RollingHash(s).search_all(t);
  vector<i64> dp(s.size());
  vector<bool> mp(s.size());
  i64 m = t.size();
  for (i64 i : ms) {
    mp[i] = true;
  }
  i64 ans = 0;
  for (i64 i = 0; i < s.size(); ++i) {
    if (mp[i]) {
      dp[i]++;
      if (i - m >= 0) dp[i] += dp[i - m];
    }
    if (i < 2 * n) {
      ans = max(ans, dp[i]);
    } else if (ans < dp[i]) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}


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

struct Node{
  int key;
  struct Node *next;
  struct Node *prev;
};

struct Node *nil;

struct Node* listSearch(int key){
  struct Node *cur = nil->next;
  while (cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void iii(void) {
  nil = (struct Node *)malloc(sizeof(struct Node));
  nil->next = nil;
  nil->prev = nil;
}

void plist(void){
  struct Node *cur = nil->next;
  int isf = 0;
  while(1){
    if(cur==nil)break;
    if(isf++>0)
      printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void ddd(struct Node *t){
  if(t==nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void insert(int key){
  struct Node *x = (struct Node *)malloc(sizeof(struct Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key, n, i;
  int size = 0, np=0, nd=0;
  char com[20];

  scanf("%d",&n);
  iii();
  for(i=0; i<n; i++){
    scanf("%s%d", com, &key);
    if(com[0]=='i'){
      insert(key);
      np++;
      size++;
    } else if (com[0]=='d'){
      if(strlen(com)>6){
        if(com[6]=='F')
          ddd(nil->next);
        else if(com[6]=='L')
          ddd(nil->prev);
      } else {
        ddd(listSearch(key));
        nd++;
      }
      size--;
    }
  }
  plist();
  return 0;
}

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

int main() {
  string s,t,u;
  int a, b;

  cin >> s >> t;
  cin >> a >> b;
  cin >> u;
  if (u==s) a--;
  if (u==t) b--;
  cout << a << ' ' << b << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;
const int INF = 1 << 30;

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

    int n, m, x;
    cin >> n >> m >> x;

    vector<int> c(n, 0);
    vector<vector<int> > a(n, vector<int>(m, 0));
    REP(i, n) {
        cin >> c[i];
        REP(j, m) cin >> a[i][j];
    }

    int ans = INF;
    REP(mask, 1 << n) {
        vector<int> level(m, 0);
        int cost = 0;
        REP(i, n) {
            if ((mask >> i) & 1) {
                cost += c[i];
                REP(j, m) level[j] += a[i][j];
            }
        }
        bool ok = true;
        REP(j, m) if (level[j] < x) ok = false;
        if (ok) ans = min(ans, cost);
    }

    if (ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3660
seq = gets.split(" ")

# Initial stack
stack = []

seq.each{|elm|
  # elm is a number
  if elm.match(/^(\d+)$/)
    num = elm.to_i
    stack.push(num)
  # elm is an operator
  elsif ['+', '-', "*"].include?(elm)
    op = elm
    n2 = stack.pop
    n1 = stack.pop
    case op
    when '+'
      stack.push(n1 + n2)
    when '-'
      stack.push(n1 - n2)
    when '*'
      stack.push(n1 * n2)
    end
  end
}

# Get answer
answer = stack[0]
puts(answer)



Measured memory_bytes: 8908
#![allow(unused_imports)]
#![allow(dead_code)]

use std::collections::*;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let (n, k): (i64, i64) = (sc.read(), sc.read());
    let ans: i64 = if k == 0 {
        n * n
    } else {
        (k + 1..n + 1)
            .map(|b| {
                let temp1 = (n / b) * (b - k);
                let temp2 = std::cmp::max(0, n % b - k + 1);
                temp1 + temp2
            })
            .sum()
    };
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }

        static void SolveA(string[] args)
        {
            int[] abcd = ReadAndParseIntArr();
            int a = abcd[0];
            int b = abcd[1];
            int c = abcd[2];
            int d = abcd[3];

            if (Check(a, b, c, d))
            {
                Console.WriteLine("Yes");
            }else
            {
                Console.WriteLine("No");
            }
        }
        private static bool Check(int a, int b, int c, int d)
        {
            if( Math.Abs(a-c) <= d) { return true; }
            if( Math.Abs(a-b) <= d && Math.Abs(b-c) <= d) { return true; }
            return false;
        }
    }
}


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

int main(){
	int N;
	int X;
	int Y=0;
	int Z=0;
	int ans = 1;
	cin >> N;
	cin >> X;
	int A[110];
	int L[110];
	for(int i=1; i<=N; i++){
		cin >> A[i];
	}
	L[1]=0;
	for(int i=2; i<N+5; i++){
		L[i] = L[i-1]+A[i-1];
		if(L[i]>X){
			ans = i-1;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int i;
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int identical = 0;
  for (i = 1; i < n; i++) {
    if (a[i] == a[i - 1]) {
      identical++;
    }
  }
  cout << (identical % 2 == 0 ? n - identical : n - identical - 1) << endl;
  return 0;
}


Measured memory_bytes: 640
import collections
n = int(input())
#a = list(map(int,input().split()))
w = [input() for _ in range(n)]
c = collections.Counter(w)
k = c.most_common()
cnt = k[0][1]

ans = []
for i,j in k:
    if j == cnt:
        ans.append(i)
ans.sort()

for i in ans:
    print(i)

Measured memory_bytes: 47636
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.20f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;



int main() {
	int n;
    cin >> n;
    ll a[n];
    rep (i, n) cin >> a[i];

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                vector<ll> b;
                b.pb(a[i]);
                b.pb(a[j]);
                b.pb(a[k]);
                sort(rng(b));
                if (b[2] < b[0] + b[1] && b[0] != b[1] && b[1] != b[2] && b[2] != b[0]) cnt++;
            }
        }
    }

    cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3632
package main

import (
  "fmt"
)

func main() {
  var a, b, c, d int
  fmt.Scan(&a, &b, &c, &d)
  l, r := a + b, c + d
  var ans string
  if l == r {
    ans = "Balanced"
  } else if l > r {
    ans = "Left"
  } else {
    ans = "Right"
  }
  fmt.Println(ans)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;
using p = pair<int, int>;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}

template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

void dijkstra(const vector<vector<int>>& g, vector<vector<bool>>& used, int s){
  const int n = (int)g.size();
  vector<int> bv(n, -1), dis(n, numeric_limits<int>::max());

  priority_queue<p, vector<p>, greater<p>> pq;
  dis[s] = 0; pq.push({0, s});

  while(!pq.empty()){
    p top = pq.top(); pq.pop();
    const int v = top.second, d = top.first;
    REP(u, n){
      if(v == u || g[v][u] == -1) continue;
      int nd = d + g[v][u];
      if(dis[u] > nd){
        dis[u] = nd;
        bv[u] = v;
        pq.push({nd, u});
      }
    }
  }

  REP(i, n){
    int v = i;
    while(bv[v] != -1){
      used[bv[v]][v] = used[v][bv[v]] = true;
      v = bv[v];
    }
  }
}

int main() {
  int n, m; cin >> n >> m;
  auto g = make_v(n, n, -1);

  REP(i, m){
    int a, b, c; cin >> a >> b >> c;
    --a; --b;
    g[a][b] = g[b][a] = c;
  }

  auto used = make_v(n, n, false);

  REP(i, n) dijkstra(g, used, i);

  int ans = 0;
  REP(s, n)REP(t, n){
    if(g[s][t] != -1 && !used[s][t]) ans++;
  }
  
  cout << ans / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1000000000000000001
#define ll long long
#define pll pair<ll, ll>
using namespace std;

struct edge {ll to, cost;};

//=============dijkstra============================
void dijkstra(ll s, ll V, vector<vector<edge>>& G, vector<vector<bool>>& used)
{
  vector<ll> d(V, INF);
  typedef pair<ll, ll> P;// first は最短距離　second は頂点の番号
  priority_queue<P, vector<P>, greater<P>> que;
  d.at(s) = 0;
  que.push(P(0, s));
  while (!que.empty())
  {
    P p = que.top();
    que.pop();
    ll v = p.second;
    if (d.at(v) < p.first) continue;
    for (ll i = 0; i < G.at(v).size(); ++i)
    {
      edge e = G.at(v).at(i);
      if (d.at(e.to) > d.at(v) + e.cost)
      {
        // cout << "V" << v << "e.to" << e.to << endl;
        // cout << d.at(e.to) << ' ' << d.at(v) + e.cost << endl;
        d.at(e.to) = d.at(v) + e.cost;
        que.push(P(d.at(e.to), e.to));
      }
    }
  }
  for (ll i = 0; i < V; ++i)
  {
    for (ll j = 0; j < G.at(i).size(); ++j)
    {
      edge e = G.at(i).at(j);
      if (d.at(i) + e.cost == d.at(e.to))
      {
        used.at(i).at(e.to) = true;
        used.at(e.to).at(i) = true;
      }
    }
  }
}
//=================================================

int main()
{
  ll N, M;
  cin >> N >> M;
  vector<vector<edge>> G(N);
  for (ll i = 0; i < M; ++i)
  {
    ll a, b, c;
    cin >> a >> b >> c;
    G.at(a - 1).push_back({b - 1, c});
    G.at(b - 1).push_back({a - 1, c});
  }
  vector<vector<bool>> used(N, vector<bool>(N, false));
  for (ll i = 0; i < N; ++i)
  {
    dijkstra(i, N, G, used);
  }
  ll ans = M;
  for (ll i = 0; i < N - 1; ++i)
  {
    for (ll j = i + 1; j < N; ++j)
    {
      if (used.at(i).at(j))
      {
        ans -= 1;
      }
    }
  }
  cout << ans << endl;
  // for (ll i = 0; i < N; ++i)
  // {
  //   for (ll j = 0; j < N; ++j)
  //   {
  //     if (used.at(i).at(j))
  //     {
  //       cout << "T";
  //     }
  //     else
  //     {
  //       cout << "F";
  //     }
  //   }
  //   cout << endl;
  // }
}


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

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int id = 0;
            var diceCommand = new DiceCommand();

            var diceList = Console.ReadLine().Split(' ').Select(n => new Dice(++id, int.Parse(n))).ToList();
            foreach (var item in Console.ReadLine().ToArray())
            {
                diceCommand.Exec(item);
            }
            
            Console.WriteLine(diceList.SingleOrDefault(n => n.Id == diceCommand.Top).Number);

            Console.ReadKey();
        }
    }

    class DiceCommand
    {
        public int Top = 1;
        public int S = 2;
        public int E = 3;

        const int diceUpDownSum = 7;

        public DiceCommand()
        {
        }

        public DiceCommand(int top, int s, int e)
        {
            Top = top;
            S = s;
            E = e;
        }

        public void Exec(char command)
        {
            switch (command)
            {
                case 'S':
                    RollDice(ref Top, ref S);
                    break;
                case 'E':
                    RollDice(ref Top, ref E);
                    break;
                case 'W':
                    RollDice(ref E, ref Top);
                    break;
                case 'N':
                    RollDice(ref S, ref Top);
                    break;
            }

        }

        void RollDice(ref int main, ref int sub)
        {
            int work = main;
            main = diceUpDownSum - sub;
            sub = work;
        }
    }

    class Dice
    {
        public int Id { get; set; }
        public int Number { get; set; }

        public Dice(int id, int number)
        {
            Id = id;
            Number = number;
        }
    }
}

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

using namespace std ;

int main () {
    string S ; cin >> S ;
    //getline(cin,S);
    int size = S.size()  ;
    int score = 0 ;
    int max = 0 ;
    for (int i = 0 ; i < size ; i ++){
        if (S[i] == 'A' || S[i] == 'C' || S[i]=='G' ||S[i]== 'T'){
            score = score  + 1 ;  
        }
        else{
                if (max < score ){ max = score ;}
                score = 0 ;
                //cout << max << endl ;
        }
    }
                if (max < score ){ max = score ;}
                score = 0 ;
                cout << max << endl ;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=220000;
const int MAXM=11000000;
const ll INF=1E18;
int n, m, a[MAXN];
struct Edge1
{
	int to, val;
	Edge1(int v, int w): to(v), val(w) {}
};
vector<Edge1> g[MAXN];
struct Edge2
{
	int u, v; ll w;
	Edge2() {}
	Edge2(int a, int b, ll c):
		u(a), v(b), w(c) {}
	bool operator < (const Edge2& rhs) const
	{
		return w<rhs.w;
	}
} ed[MAXM];
struct DSU
{
	int f[MAXN];
	void init()
	{
		for (int i=1; i<=n; i++) f[i]=i;
	}
	int getf(int x)
	{
		if (x==f[x]) return x;
		return f[x]=getf(f[x]);
	}
	bool merge(int u, int v)
	{
		int x=getf(u), y=getf(v);
		if (x==y) return 0;
		f[x]=y; return 1;
	}
} dsu;
bool vis[MAXN];
int sz[MAXN], mx[MAXN];
ll dis[MAXN];
int sum, root, pos; ll mn;
void getroot(int u, int f)
{
	sz[u]=1, mx[u]=0;
	for (Edge1 e:g[u])
	{
		int v=e.to;
		if (!vis[v]&&v!=f)
		{
			getroot(v, u); sz[u]+=sz[v];
			mx[u]=max(mx[u], sz[v]);
		}
	}
	mx[u]=max(mx[u], sum-sz[u]);
	if (mx[u]<mx[root]) root=u;
}
void getpos(int u, int f)
{
	if (a[u]+dis[u]<mn) mn=a[u]+dis[u], pos=u;
	for (Edge1 e:g[u])
	{
		int v=e.to;
		if (!vis[v]&&v!=f)
		{
			dis[v]=dis[u]+e.val;
			getpos(v, u);
		}
	}
}
void link(int u, int f)
{
	ed[++m]=Edge2(u, pos, a[u]+a[pos]+dis[u]+dis[pos]);
	for (Edge1 e:g[u])
		if (!vis[e.to]&&e.to!=f) link(e.to, u);
}
void solve(int u)
{
	mn=INF, dis[u]=0;
	getpos(u, 0); link(u, 0);
	vis[u]=1;
	for (Edge1 e:g[u])
	{
		int v=e.to;
		if (!vis[v])
		{
			sum=sz[v], root=0;
			getroot(v, u); solve(root);
		}
	}
}
int main()
{
//	freopen("AT3611.in", "r", stdin);
//	freopen("AT3611.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
	for (int i=1; i<n; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(Edge1(v, w));
		g[v].push_back(Edge1(u, w));
	}
	mx[0]=sum=n, root=0;
	getroot(1, 0); solve(root);
	sort(ed+1, ed+m+1);
	dsu.init();
	ll ans=0;
	for (int i=1, cnt=0; i<=m&&cnt<n-1; i++)
		if (dsu.merge(ed[i].u, ed[i].v))
			cnt++, ans+=ed[i].w;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 82432
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
const long long INF = 1e18;
const double PI = 2 * asin(1);
typedef long long ll;


int main(){
  int W, H; cin >> W >> H;

  vector < pair<ll, bool> > PQ;
  for (int i = 0; i < W; i++){
    ll P; cin >> P;
    PQ.push_back(make_pair(P, true));
  }
  for (int i = 0; i < H; i++){
    ll Q; cin >> Q;
    PQ.push_back(make_pair(Q, false));
  }
  sort(PQ.begin(), PQ.end());
  
  ll ans = 0;
  ll T = H + 1, F = W + 1;
  for (int i = 0; i < PQ.size(); i++){
    if (PQ[i].second == true){
      ans += PQ[i].first * T;
      F--;
    }else{
      ans += PQ[i].first * F;
      T--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6256
my ($N, $M) =  split(' ', <>);

my @shop_tmp;
for ( 1.. $N) {
    my ($A, $B) =  split(' ', <>);
    push @shop_tmp, [$A, $B];
}

my @shop = sort { $a->[0] <=> $b->[0] } @shop_tmp;

my $got = 0;
my $pay_total = 0;

SHOP:
for my $r ( @shop ) {
    my $B_max = $r->[1];
    my $buy_num = $M - $got > $B_max ? $B_max : $M - $got;
    $pay_total += $r->[0] * $buy_num;
    $got += $buy_num;
    last SHOP if $got >= $M;
}

print $pay_total;

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

int main()
{
	int A, B;
	cin >> A >> B;

	if (0 == B % A) {
		cout << A + B <<endl;
	} else {
		cout << B - A <<endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s=to_string(n);
    for(int i=0;i<3;i++)
    {
        if(s[i]=='7')
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
 ll N, ans=0;
string str;
 signed main(){
    cin >> N >> str;
    for(int i=0;i<str.size()-2;i++) {
        if(str[i]=='A'&&str[i+1]=='B'&&str[i+2]=='C') ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
double len(double x1,double x2,double y1,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
	int N;
	double x[100],y[100];
	scan(N);
	rep(i,N){
		scan(x[i]>>y[i]);
	}
	int facN=1;
	rep1(i,N) facN*=i;
	vint p;
	rep(i,N) p.push_back(i);
	double sum=0;
	do{
		rep(i,N-1){
			sum+=len(x[p[i]],x[p[i+1]],y[p[i]],y[p[i+1]]);
		}
	}while(next_permutation(ALL(p)));
	prin(setprecision(12)<<sum/facN);
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from collections import defaultdict

n = int(input())
pairs = list()
patterns = defaultdict(int)

for _ in range(n):
    pairs.append(tuple((map(int, input().split()))))

for i in range(n):
    for j in range(n):
        if i != j:
            patterns[(pairs[i][0] - pairs[j][0], pairs[i][1] - pairs[j][1])] += 1

ans = 1
if n > 1:
    ans = n - max(patterns.values())

print(ans)

Measured memory_bytes: 39408
from itertools import groupby

s = input()
k = int(input())

t = [(k, len(list(v))) for k, v in groupby(s)]
ans = 0
if len(t) == 1:
    ans += t[0][1] * k // 2
else:
    if t[0][0] == t[-1][0] and t[0][1] % 2 == 1 and t[-1][1] % 2 == 1:
        ans += k - 1
    ans += sum(v[1] // 2 for v in t) * k
print(ans)




Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<ll> A(3 * N);
  for (auto &it : A)
    cin >> it;

  vector<pair<ll, ll>> score(N + 1);
  ll sum_front = 0;
  priority_queue<ll, vector<ll>, greater<ll>> que_front;
  for (int i = 0; i < N; i++)
  {
    sum_front += A[i];
    que_front.push(A[i]);
  }
  score[0].first = sum_front;

  for (int k = N; k < 2 * N; k++)
  {
    sum_front += A[k];
    que_front.push(A[k]);
    sum_front -= que_front.top();
    que_front.pop();
    score[k - (N - 1)].first = sum_front;
  }

  ll sum_back = 0;
  priority_queue<ll> que_back;
  for (int i = 2 * N; i < 3 * N; i++)
  {
    sum_back += A[i];
    que_back.push(A[i]);
  }
  score[N].second = sum_back;

  for (int k = 2 * N - 1; k >= N; k--)
  {
    sum_back += A[k];
    que_back.push(A[k]);
    sum_back -= que_back.top();
    que_back.pop();
    score[k - N].second = sum_back;
  }

  ll ans = -INF;
  for (int i = 0; i < N + 1; i++)
  {
    ans = max(ans, score[i].first - score[i].second);
  }
  // cerr << score[1].first << " " << score[1].second << endl;
  cout << ans << endl;
  return 0;
}

// aの前半k要素は黒色または赤色のみで，aの後半3N - k要素は黒色または青色のみである．この条件が成り立つような整数kをN<=k<=2Nの範囲で全探索する．各kについて答えを求められればそれらの最大値が全体の答えとなる．kを一つ固定する．あらかじめ，aの前半N要素をpushしておく．また現在キューに入っている要素の総和を保持しておく．要素akをpushしたあと，最小をpopすればよい．総和も足し引きする．青も同様．2*N - N + 1 = N + 1


Measured memory_bytes: 9464
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K;
  string S;
  string sw;
  
  cin>>K>>S;
  
  if(S.size()<=K){
    cout<<S<<endl;
  }else{
    for(int i=0;i<K;i++){
      sw=sw+S.at(i);
    }
    sw=sw+"...";
    cout<<sw<<endl;
  }
    
  
}




Measured memory_bytes: 3624
// pE
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Scanner scanner;
	int inf = (int)1e9;

	public Solution() {
		scanner = new Scanner(System.in);

		// scanner.nextLine();
		while (scanner.hasNext()) {
			run_case();
		}
	}
	private void run_case() {
		// scanner.nextLine();
		String line = scanner.nextLine();

		int H = Integer.parseInt(line.split("\\s+")[0]);
		int N = Integer.parseInt(line.split("\\s+")[1]);

		List<Spell> spells = new ArrayList<>();
		for (int i=0; i<N; i++) {
			// spells[i] = Integer.parseInt(scanner.nextLine().split("\\s+")[0]);
			line = scanner.nextLine();
			int a = Integer.parseInt(line.split("\\s+")[0]);
			int b = Integer.parseInt(line.split("\\s+")[1]);
			spells.add(new Spell(a, b));
		}
		// System.out.println(Arrays.toString(spells));

		// HashMap<String, Integer> mem = new HashMap<>();
		int[][] mem = new int[N][H+1];
		for (int i=0; i<N; i++) Arrays.fill(mem[i], -1);

		int res = dfs(0, spells, H, mem);
		System.out.println(res);

		return;
	}

	public int dfs(int idx, List<Spell> spells, int monsterHealth, int[][] mem) {
		if (monsterHealth <= 0) return 0;
		if (idx == spells.size()) return inf;

		// String key = String.valueOf(idx) + "_" + String.valueOf(monsterHealth);
		// if (mem.containsKey(key)) return mem.get(key);
		if (mem[idx][monsterHealth] != -1) return mem[idx][monsterHealth];

		int res = (int)1e9;
		// use
		int t = dfs(idx, spells, monsterHealth - spells.get(idx).power, mem);
		if (t != inf) res = Math.min(res, spells.get(idx).cost + t);
		// pass
		t = dfs(idx + 1, spells, monsterHealth, mem);
		if (t != inf) res = Math.min(res, t);

		// mem.put(key, res);
		// return res;
		return mem[idx][monsterHealth] = res;
	}

	private int[] strToIntArray(String str) {
	    String[] vals = str.split("\\s+");
	    int sz = vals.length;
	    int[] res = new int[sz];
	    for (int i=0; i<sz; i++) {
	        res[i] = Integer.parseInt(vals[i]);
	    }
	    return res;
	}
}
class Spell {
	public int power, cost;
	public Spell(int power, int cost) {
		this.power = power;
		this.cost = cost;
	}
}


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

 
int main(){
  
 int n; cin >> n;
 std::vector<int> v(n);
 for(int i = 0; i < n; i++){
  cin >> v[i];
 }

 for(int i=0; i<n-1; i++){
  if(v[i+1]>v[i])
    v[i+1]-=1;
 }

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


}

Measured memory_bytes: 640
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
using namespace std;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;
 
typedef long long int ll;
const ll N = 2e5 + 9;
// const ll m = 1e9 + 7;
const ll inf= 1ll<<62;
#define x first
#define y second
#define pb push_back
#define mp make_pair
using pii = pair<ll, ll>;
const ll mod = 1e9+7;
ll powm(ll a, ll b) { a = a%mod;ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
ll fk(ll n,ll k){
     ll a = (k*(k-1))/2;
     return a;
}
ll lk(ll n,ll k){
     ll a = (k*n) - fk(n,k);
     return a;
}
int main()
{   
                               
     ll T= 1;
     // cin>>T;
     ll ca = 1;
     while(T--){
          ll n,k;cin>>n>>k;
          ll ans= 0;
          for(int i = k;i<=n+1;i++){
               ans+=(lk(n,i) - fk(n,i) +1);
               ans%=mod;
          }
          cout<<ans<<'\n';
     }
    return 0;
}

Measured memory_bytes: 3640
n = int(input())
heights = list(map(int, input().split()))

def nextgen(comb):
    lis = comb[0]
    j = comb[1]
    if len(lis) == 1 and lis[0] != 0:
        j += 1  
    for i in range(len(lis)-1):
        if (i != len(lis) and (lis[i] == 0 and lis[i+1] != 0)) or (i == 0 and lis[i] != 0):
            j += 1
        if lis[i] != 0:
            lis[i] -= 1
    if lis[len(lis)-1] != 0:
        lis[len(lis)-1] -= 1
    return [lis, j]

comb = [heights, 0]
while (comb[0].count(0) != len(comb[0])):
    comb = nextgen(comb)

print(comb[1])

Measured memory_bytes: 3064
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N, P;
int A[1<<18];
int X[1<<18][2];
int buf[9];
struct Cmp {
    bool operator()(int i, int j) {
	if (i == -1) return false;
	if (j == -1) return true;
	return A[i] > A[j];
    }
} cmp;

void MAIN() {
    scanf("%d", &N);
    P = 1<<N;
    REP (i, P) scanf("%d", A+i);

    REP (s, P) {
	X[s][0] = s;
	X[s][1] = -1;
    }

    REP (t, N) REP (s, P) if (~s>>t&1) {
	int ns = s | (1<<t);
	buf[0] = X[s][0];
	buf[1] = X[s][1];
	buf[2] = X[ns][0];
	buf[3] = X[ns][1];
	sort(buf, buf+4, cmp);
	int len = unique(buf, buf+4) - buf;
	buf[len] = -1;
	X[ns][0] = buf[0];
	X[ns][1] = buf[1];
    }
    int ma = 0;
    for (int s=1; s<P; s++) {
	amax(ma, A[X[s][0]] + A[X[s][1]]);
	printf("%d\n", ma);
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 6144
import java.io.*
import java.util.*

fun solve(N: Int, M: Int, x: LongArray, y: LongArray, z: LongArray){
    val xyz = (0 until N).map { Triple(x[it], y[it], z[it]) }
    // +++ ++- +-- ... の場合全てを試す
    val ops = listOf<(Long) -> Long>({x -> x}, {x -> -x})
    val patterns = product(ops, ops, ops)
    var ans = 0L
    for (pattern in patterns){
        val ret = xyz.map{
            pattern[0](it.first) + pattern[1](it.second) + pattern[2](it.third)
        }.sortedDescending()
        ans = Math.max(ans, ret.slice(0 until M).sum())
    }
    println(ans)
    return
}


fun <T> product(vararg lists: List<T>): List<List<T>> {
    fun <T> oneDimTimesOne(left: List<T>, right: List<T>): List<List<T>> =
            left.flatMap { lelem -> right.map { relem -> listOf(lelem, relem) } }

    fun <T> twoDimTimesOne(left: List<List<T>>, right: List<T>): List<List<T>> {
        val product = mutableListOf<List<T>>()
        for (list in left) {
            for (element in right) {
                product.add(list + listOf(element))
            }
        }
        return product
    }
    require(lists.size >= 2)
    return lists
            .drop(2)
            .fold(oneDimTimesOne(lists[0], lists[1])) { acc, suc -> twoDimTimesOne(acc, suc) }
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toLong()
    val M = sc.next().toLong()
    val x = LongArray(N.toInt())
    val y = LongArray(N.toInt())
    val z = LongArray(N.toInt())
    for (i in 0 until N.toInt()) {
        x[i] = sc.next().toLong()
        y[i] = sc.next().toLong()
        z[i] = sc.next().toLong()
    }
    solve(N.toInt(), M.toInt(), x, y, z)
}



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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define MINS(m, s) m.insert(mp(s, 1));
#define MFIN(m, s) m.find(s) != m.end()
#define INF (1 << 29)
const int mod = 1000000007;

int main() {
    ll n, ac, tle, wa, re;
    ac = 0, tle = 0, wa = 0, re = 0;
    string s;

    cin >> n;
    for(ll i = 0; i < n; i++) {
        cin >> s;
        if(s == "AC") {
            ac++;
        } else if(s == "WA") {
            wa++;
        } else if(s == "TLE") {
            tle++;
        } else {
            re++;
        }
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}

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

using ll = long long;
const ll MOD = 1e9 + 7;

// 繰り返し自乗法(x^nをmで割った余り) O(logn)
ll power(ll x, ll n, ll m) {
  ll res = 1;
  if (n > 0) {
    res = power(x, n / 2, m);
    if (n % 2 == 0) res = (res * res) % m;
    else res = (((res * res) % m) * x) % m;
  }
  return res;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, k;
  cin >> n >> k;
  
  ll ans = 0;
  vector<ll> x(k + 1);
  for (ll i = k; i > 0; i--) {
    ll keep = power(k / i, n, MOD);
    keep += (ll) MOD * 100000;
    for (ll j = 2; j * i <= k; j++) {
      keep -= x.at(j * i);
    }
    keep %= MOD;
    x.at(i) = keep;
    ans += (keep * i) % MOD;
    ans %= MOD;
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 3992
N = int(input())
es = [[] for _ in range(N)]
H = []
for i in range(N-1):
  a,b = map(int,input().split())
  if a > b:
    a,b = b,a
  a-=1;b-=1
  #es[a].append(b)
  #es[b].append(a)
  H.append([a,b])

ten = N*(N+1)*(N+2)//6
hen = 0
for i in range(N-1):
  p,q = H[i]
  hen += (p+1)*(N-1-q+1)
ans = ten -hen
print(ans)

Measured memory_bytes: 53448
import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

private val fact = arrayOf(0, 1, 2, 6, 24, 120, 720, 5040, 40320)
private var less = arrayOf<Int>()

private fun index(n: Int, items: Array<Int>): Int {
    less = Array(n) { it }
    var res = 1
    for (i in 0 until n) {
        val item = items[i] - 1
        res += less[item] * fact[n - 1 - i]
        for (j in item + 1 until n) {
            --less[j]
        }
    }
    return res
}

private fun solve() {
    val n = nextInt()
    val p = Array(n) { nextInt() }
    val q = Array(n) { nextInt() }
    println(Math.abs(index(n, p) - index(n, q)))
}

fun main(args: Array<String>) {
    solve()
    out.close()
}

private var br = BufferedReader(InputStreamReader(System.`in`))
private var st: StringTokenizer? = null
private var out = PrintWriter(System.out)

@Throws(IOException::class)
private fun next(): String {
    while (st == null || !st!!.hasMoreTokens()) {
        st = StringTokenizer(br.readLine())
    }
    return st!!.nextToken()
}

@Throws(IOException::class)
private fun nextInt(): Int {
    return next().toInt()
}

@Throws(IOException::class)
private fun nextLong(): Long {
    return next().toLong()
}


Measured memory_bytes: 31400
#ABC099-D Good Grid
"""
問題：
条件を満たすようにc色の色を塗り替える場合に生じるコスト(違和感)
を最小化する。
条件：
ある任意の２箇所のグリッド grid[a][b]とgrid[c][d]を見た時に、
(a+b)%3 == (c+d)%3 ならば、その２箇所は同じ色である必要があり、
そうでない場合は違う色である必要がある。
6*6のグラフで見るとこんな感じになる
012012
120120
201201
012012
120120
201201 

解法：
色が30色であるという制約から、
30C3通りを試した時のコストの最小値が答えになる。
500*500のgridで高速に計算する必要があるため、
予めdictを用いて3で割った余りが0,1,2の場所に何の色が何個入っているか
を求めておき、あとはそれぞれの場所から変更先の色へのコストを求めれば
良い。
"""
import sys
from collections import defaultdict
import itertools
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,c = map(int,readline().split()) #N*Nの正方行列,c色
D = [] #隣接リスト(ある色iから色jに塗り替えた時の違和感D[i][j])
#ちなみに、塗り替えなかった場合違和感は0になる
for i in range(c):
    D.append(list(map(int,readline().split())))

grid = [] #元の色のグリッド(1-indexed)
for i in range(n):
    grid.append(list(map(int,readline().split())))



dic_0 = defaultdict(int)
dic_1 = defaultdict(int)
dic_2 = defaultdict(int)

for i in range(n):
    for j in range(n):
        if (i+j)%3 == 0:
            dic_0[grid[i][j]] += 1
        elif (i+j)%3 == 1:
            dic_1[grid[i][j]] += 1
        else:
            dic_2[grid[i][j]] += 1

colors = [i for i in range(1,c+1)]
ans = 10**9
for i,j,k in itertools.combinations(colors,3):
    for o,p,q in itertools.permutations([i,j,k]):
        res = 0
        for a,b in dic_0.items():
            res += D[a-1][o-1]*b
        for a,b in dic_1.items():
            res += D[a-1][p-1]*b
        for a,b in dic_2.items():
            res += D[a-1][q-1]*b

        ans = min(ans,res)

print(ans)


Measured memory_bytes: 45180
# ABC099A
A = int(input())
# A, B = map(int, input().split())

coins = [0]
mon = (1,6,9,36,81,216,729,1296,6561,7776,46656,59049)

for i in range(1,A+1):
    least=100
    for j in mon:
        if(len(coins)>=j):
            if(coins[i-j]<least):
                least=coins[i-j]
        else:
            break;
    coins.append(least+1)

print(coins[A])


Measured memory_bytes: 3860
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = min(a[0], b[0])
tmp = max(0, b[0]-a[0])

for i in range(1,n):
  if tmp > a[i]:
    ans += a[i]
    tmp = b[i]
  else:
    ans += tmp
    m = a[i]-tmp
    ans += min(m, b[i])
    tmp = max(0, b[i]-m)
ans += min(a[n], tmp)
print(ans)

Measured memory_bytes: 19156
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;

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;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main( ){
    ll N,K; cin>>N>>K;
    ll v=min(N%K,abs(N%K-K));
    cout<<v<<endl;
   return 0;
}




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

using namespace std;

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

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

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

void solve(long long N, std::vector<long long> x, std::vector<long long> y) {

    set<ll> S[2][2];
    for (int i = 0; i < N; i++) {
        S[1][0].insert(x[i] - y[i]);
        S[1][1].insert(x[i] + y[i]);
        S[0][1].insert(-x[i] + y[i]);
        S[0][0].insert(-x[i] - y[i]);
    }

    ll ans = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ans = max(ans, *S[i][j].rbegin() + *S[i^1][j^1].rbegin());
        }
    }
    cout << ans << endl;
}

int main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &x[i]);
        scanf("%lld", &y[i]);
    }
    solve(N, std::move(x), std::move(y));
    return 0;
}


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

char in[120];
pair<pair<string, int> , int> p[110];

int main(void)
{
    int a; scanf("%d", &a);
    
    for (int i = 0; i < a; i++)
    {
        int t; scanf("%s%d", in, &t);
        p[i] = make_pair(make_pair(in, -t), i);
    }
    
    sort(p, p + a);
    for (int i = 0; i < a; i++) printf("%d\n", p[i].second + 1);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n,k;
  cin >> n >> k;
  k--;
  vi data(n);
  rep(i,n) cin >> data[i];
  int basho;
  rep(i,n) {
    if(data[i] == 1) basho = i;
  }
  int left = basho;
  int right = data.size()- 1- basho;
  int ans = 0;
  int cent = 0;
  ans += left / k;
  cent += left % k;
  ans += right / k;
  cent += right % k;
  if(cent > k) ans += 2;
  else if(cent != 0) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 640
#[allow(unused_imports)]
use std::cmp::max;
#[allow(unused_imports)]
use std::cmp::min;
#[allow(unused_imports)]
use std::fmt;
#[allow(unused_imports)]
use std::fmt::Debug;
#[allow(unused_imports)]
use std::io;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
    let n: i64 = get_vec_input()[0];
    let mut a: Vec<i64> = get_vec_input();
    a.sort();
    let a_max = a[n as usize - 1];
    let mut dp: Vec<bool> = vec![true; (a_max + 1) as usize];
    let mut count_dp: Vec<i64> = vec![0; (a_max + 1) as usize];

    for &x in a.iter() {
        count_dp[x as usize] += 1;
        for i in 2..=a_max {
            if x * i <= a_max {
                if dp[(x * i) as usize] == false {
                    continue;
                }
                dp[(x * i) as usize] = false;
            } else {
                break;
            }
        }
    }

    if a.len() == 1 {
        println!("1");
        return;
    }

    let result = a
        .iter()
        .map(|&x| x as usize)
        .filter(|&x| count_dp[x] <= 1)
        .filter(|&x| dp[x] == true)
        .collect::<Vec<_>>()
        .len();

    println!("{}", result);
}

#[allow(dead_code)]
fn check_prime(value: i64) -> bool {
    if value == 2 {
        return true;
    }
    if value % 2 == 0 {
        return false;
    }
    for i in 3..(value as f64).sqrt().floor() as i64 {
        if value % i == 0 {
            return false;
        }
    }
    return true;
}

#[allow(dead_code)]
fn get_digit(value: i64) -> i64 {
    let mut digit = 0i64;
    let mut value = value;
    while value != 0 {
        value /= 10;
        digit += 1;
    }
    digit
}

#[allow(dead_code)]
fn sum_digit2(value: String) -> u32 {
    return value.chars().fold(0u32, |a, b| a + b.to_digit(10).unwrap());
}

#[allow(dead_code)]
fn sum_digit(value: i64) -> i64 {
    if value < 10 {
        return value;
    }
    return sum_digit(value / 10) + value % 10;
}

#[allow(dead_code)]
fn update_max<T>(left: &mut T, right: T)
where
    T: std::cmp::Ord + std::clone::Clone,
{
    if *left < right {
        *left = right.clone();
    }
}

#[allow(dead_code)]
fn update_min<T>(left: &mut T, right: T)
where
    T: std::cmp::Ord + std::clone::Clone,
{
    if *left > right {
        *left = right.clone();
    }
}

#[allow(dead_code)]
fn get_vec_input<T>() -> Vec<T>
where
    T: FromStr,
    T::Err: Debug,
{
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read line");
    let vec: Vec<T> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    vec
}

#[allow(dead_code)]
fn get_tuple_input() -> (u64, f32) {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    let mut iter = s.trim().split_whitespace();
    let c: u64 = iter.next().unwrap().parse().unwrap();
    let n: f32 = iter.next().unwrap().parse().unwrap();
    (c, n)
}

#[allow(dead_code)]
fn get_string_input() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    s.trim().to_string()
}


Measured memory_bytes: 12828