akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque, BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let (n, ma, mb) = get!(usize, usize, usize);
    let abc = get!(usize, usize, usize;n);

    let mut dp = vec![vec![vec![usize::max_value() / 2; 401]; 401]; n + 1];
    dp[0][0][0] = 0;

    for (&(a, b, c), i) in abc.iter().zip(1..) {
        for x in 0..401 {
            for y in 0..401 {
                dp[i][x][y] = min(dp[i][x][y], dp[i - 1][x][y]);
                if x + a <= 400 && y + b <= 400 {
                    dp[i][x + a][y + b] = min(dp[i][x + a][y + b], dp[i - 1][x][y] + c);
                }
            }
        }
    }

    let mut ans = usize::max_value() / 2;

    for x in 1..401 {
        for y in 1..401 {
            if x * mb == y * ma {
                ans = min(dp[n][x][y], ans);
            }
        }
    }

    if ans == usize::max_value() / 2 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}


Measured memory_bytes: 63740
import java.io.*; 
import java.util.*; 

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String input = in.nextLine();
		System.out.println(parse(input));
	}
	
	static Integer parse(String input) {
		Stack<Integer> stack = new Stack<Integer>();
		String[] things = input.split(" ");
		for(int i = 0; i < things.length; i++) {
			if(things[i].equals("+")) {
				Integer one = stack.pop();
				Integer two = stack.pop();
				stack.push(one + two);
			} else if(things[i].equals("-")) {
				Integer one = stack.pop();
				Integer two = stack.pop();
				stack.push(two - one);
			} else if(things[i].equals("*")) {
				Integer one = stack.pop();
				Integer two = stack.pop();
				stack.push(one * two);
			} else {
				stack.push(Integer.parseInt(things[i]));
			}
		}
		return stack.pop();
	}

}



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

int main() {
  int n; cin >> n;
  int ans = 0;
  vector<int> a(n);
  rep(i,n) {
    cin >> a[i];
    a[i]--;
  }
  vector<bool> ed(n,false);
  rep(i,n) {
    if (ed[i]) continue;
    if (a[a[i]] == i) {
      ans++;
      ed[i] = true; ed[a[i]] = true;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
  lint lcm(lint a,lint b){
      return a/__gcd(a,b)*b;
  }

  int main(){
      lint N,M;
      cin>>N>>M;
      lint ans1=0,ans2=0;

      pair<lint,string> x[M];
      bool y[200000];
      bool z[200000];
      lint d[200000];
      rep(i,M){
          lint g;
          string s;
          cin>>g>>s;
          x[i]=make_pair(g,s);
      }
      rep(i,200000){
           y[i]=true;
           z[i]=false;
           d[i]=0;
      }
rep(i,M){
    lint g;
    string s;
    tie(g,s)=x[i];
    if(s=="AC"&&z[g]==false){
        ans1++;
        ans2+=d[g];
        z[g]=true;
    }
    else if(z[g]==false&&s=="WA"){
        
       d[g]++;
    }

}

cout<<ans1<<" "<<ans2;

        
  }
  

Measured memory_bytes: 8192
def c_forbidden_list(RANGE=50):
    X, N = [int(i) for i in input().split()]
    P = set([int(i) for i in input().split()]) if N != 0 else set()

    for t in range(RANGE + 1):
        if X - t not in P:
            return X - t
        elif X + t not in P:
            return X + t
    return None  # 入力の制約上ここには来ない

print(c_forbidden_list())

Measured memory_bytes: 9192
def main():

    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    for i in range(n):
        B[A[i] - 1] = i + 1
    B = ' '.join(map(str, B))
    print(B)

if __name__ == "__main__":
    main()

Measured memory_bytes: 18372
import qualified Data.ByteString.Char8 as BS
import Data.Maybe (fromJust)
import Data.List

solve :: [Int] -> Int -> Int
solve = ((.) sum ) . (flip take) . reverse . sort

main :: IO ()
main = do
    [n, k] <- map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
    a <- map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
    print $ solve a k


Measured memory_bytes: 508
N = gets.to_i
x = gets.split(" ").map { |e| e.to_i }

copy = x.dup
copy.sort!
big = copy[N/2]
sma = copy[N/2-1]

for i in 0..N-1 do
  if x[i] < big
    puts big
  else
    puts sma
  end
end

Measured memory_bytes: 23396
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k){ll b=1;k=min(n-k,k);DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

class UnionFind {
    size_t size;
public:
    vector<size_t> node;
    UnionFind(size_t n) : node(n), size(n) {
        for(size_t i = 0; i < n; i++) node[i] = i;
    }
    size_t root(size_t x) {
        if (node[x] == x) return x;
        return node[x] = root(node[x]);
    }
    void unite(size_t x, size_t y) {
        size_t rx = root(x);
        size_t ry = root(y);
        if (rx == ry) return;
        node[rx] = ry;
    }
    bool same(size_t x, size_t y) {
        size_t rx = root(x);
        size_t ry = root(y);
        return rx == ry;
    }
};

ll N, M, K, L;

int main() {
    cin >> N >> M;
    UnionFind uf(M + N);
    REP(i, N) {
        cin >> K;
        REP(j, K) {
            cin >> L;
            uf.unite(L - 1, M + i);
        }
    }
    REP(i, N) {
        if (!uf.same(M, M + i)) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 2688
#include<stdio.h>
int main(void){
	int n,S[100000],q,T[50000],C=0,i,left,right  ,key   ,mid;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&S[i]);
	}
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&T[i]);
	}
	for(i=0;i<q;i++){
		left=0;
		right=n;
		mid=(left+right)/2;
		key=T[i];
		while(left<=right){
			if(S[mid]==key){
				C++;
				break;
			}
			if(S[mid]<key){
				left=mid+1;
			}
			else if(S[mid]>key){
				right=mid-1;
			}
			mid=(left+right)/2;
		}
	}
	printf("%d\n",C);
	return 0;
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define pb push_back
#define mp make_pair
#define fi(i,start,end) for(int i=start; i < end ; ++i)
#define Fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mod 10000000


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

	long long int x,y,ans,a,b,c,d;

	for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        if(i==0){a=x+y;b=x+y;c=x-y;d=x-y;}
        a=max(a,x+y);
        b=min(b,x+y);
        c=max(c,x-y);
        d=min(d,x-y);
    }
    cout<<max((a-b),(c-d));



}


Measured memory_bytes: 3608
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

#define ll long long
#define sz(s) (int)(s.size())
#define all(s) s.begin(), s.end()
#define mkp make_pair
#define eb emplace_back

const int N = 2e5 + 69;
const int NN = 2e3 + 69;
const int INF = 1e6 + 9;
const ll INF_LONG = 1e18;
const int mod = 1e9 + 7;
const int BLOCK = 174;

#define int ll

int a[N];

void solve() {
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		sum += a[i];
	}
	if (sum % 10 != 0) {
		cout << sum << '\n';
		return;
	}
	int mx = 0;
	for (int i = 1; i <= n; ++ i) {
		int x = sum - a[i];
		if (x % 10 != 0)
			mx = max(mx, x);
	}
	cout << mx << '\n';
}

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}


Measured memory_bytes: 256
A, B, M=map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
xyc=[list(map(int, input().split())) for _ in range(M)]
xyc.sort(key=lambda x:(x[0], x[1], x[2]))
ans=min(a)+min(b)

for i in range(M):
    x, y, c = xyc[i]
    ans=min(ans, a[x-1]+b[y-1]-c)
print(ans)

Measured memory_bytes: 93244
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

int gcd(int x, int y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    int r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//for(int i = ; i < ; i++){}

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <utility>
using namespace std;
 
int main() {
  int n, m;
  cin >> n >> m;
  
  vector<int> a(n);
  float tokuhyo = 0;
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    tokuhyo += a.at(i);
  }
  
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (a.at(j) < a.at(j + 1))
        swap(a.at(j), a.at(j + 1));
    }
  }
  
  int b = 0;
  for (int i = 0; i < m; i++) {
    if (a.at(i) < tokuhyo / (4 * m))
      b += 1;
  }
  
  if (b == 0)
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;
}

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

using namespace std;

bool check(string part_S, string T){
	for (int i=0; i<T.size(); i++){
		if ((part_S[i] != '?') && (part_S[i] != T[i])){
			return false;
		}
	}
	return true;
}

string merge(string S, string T, int left){
	for (int i=0; i<S.size(); i++){
		if (S[i] == '?'){
			S[i] = 'a';
		}
	}

	for (int j=0; j<T.size(); j++){
		S[j + left] = T[j];
	}

	return S;
}

int main(){
	string S;
	string T;

	cin >> S;
	cin >> T;

	if (S.size() < T.size()){
		cout << "UNRESTORABLE" << endl;
	}
	else{
		for (int i=S.size()-T.size(); i>=0; i--){
			string part_S = S.substr(i, T.size());
			if (check(part_S, T)){
				cout << merge(S, T, i) << endl;
				return 0;
			}
		}
		cout << "UNRESTORABLE" << endl;
	}

}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node tree_minimum(Node x){

    while(x->left != NULL){
      x = x->left;
    }
    return x;
}

Node tree_search(Node u, int k){

    if(u->key > k){
        if(u->left==NIL){  /* もし左側になければ，keyはない */
            return NIL;
        }
        return tree_search(u->left, k);
    }
    /* 自分より大きい値ならば，右側 */
    if(u->key < k){
        if(u->right == NULL){
            return NULL;      /* もし右側になければ，keyはない */
        }
        return tree_search(u->right, k);
    }

    return u;
}

Node tree_successor(Node x){
  Node y;
  if (x->right != NIL){
    return tree_minimum(x->right);
  }
  y = x->parent;
  while (y != NIL && x == y->right){
    x = y;
    y = y->parent;
    return y;
  }
}


void tree_delete(Node z){
  Node x,y;
  if(z != NIL){
      if(z->left == NIL || z->right == NIL){
         /* 左か右，どちらかがNULLであった場合(両方NULLの場合も含む) */
          y = z;
          if(z->left != NIL){
              x = y->right;
          } else {
             x = y->right;
          }

      } else if(x != NIL) {

          x->parent = y->parent;
          if(y->parent == NIL){
            root = x;
          } else if(y = y->parent->left){
              y->parent->left = x;
          } else {
              y->parent->right = x;
          }
      }
  }

      if (y != z){
        z->key = y->key;
        z->parent = y->parent;
        z->left = y->left;
        z->right = y->right;
      }
}

void insert(int k){

  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

    while(x != NIL){
        y = x;
        if (z->key < x->key){
            x = x->left;
        }else {
            x = x->right;
        }
    }
    z->parent = y;

    if (y == NIL){
        root = z ;
    } else if (z->key < y->key){
        y->left = z;
    } else {
        y->right = z;
    }
}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
  }
}

void preorder(Node u){
  if (u != NIL){
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = tree_search(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      tree_delete(tree_search(root, x));
    }
  }
  return 0;
}

Measured memory_bytes: 19364
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scanf("%d", &N)

	ans := 0.0

	var x float64
	var u string
	for i := 0; i < N; i++ {
		fmt.Scan(&x)
		fmt.Scan(&u)

		if u == "JPY" {
			ans += x
		} else {
			ans += x * 380000.0
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int n, k, arr[10000],sum=0;
	cin >> n >> k;
	for (int i = 0; i <n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	
	for (int i = 0; i < k; i++) {
		sum += arr[i];
	}
	cout << sum;
	return 0;
}


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

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

	int temp;
	long min = 1000000, max = -1000000, sum = 0;

	for(int i = 0; i < n; i++){
		cin >> temp;

		sum+= temp;
		if(temp < min) min = temp;
		if(max < temp) max = temp;
	}

	printf("%ld %ld %ld\n", min, max, sum);

	return 0;
}

Measured memory_bytes: 1152
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
int n;
int ar[100005];
void ng(){
  puts("NO");
  exit(0);
}

int main(){
  cin>>n;
  lint tot=0;
  REP(i,n) scanf("%d",&ar[i]),tot+=ar[i];
  lint base=n*(lint)(n+1)/2;
  if(tot%base) ng();
  lint times=tot/base;
  lint cnt=0;
  REP(i,n){
    lint dif=ar[(i+1)%n]-ar[i]-times;
    if(dif>0) ng();
    dif*=-1;
    if(dif%n) ng();
    cnt+=dif/n;
  }
  if(cnt!=times) ng();
  puts("YES");
  return 0;
}





Measured memory_bytes: 640
l, r = gets.split.map(&:to_i)
if r - l >= 2018
  p 0
  exit
end
arr = []
tmp = (l..r).to_a
tmp.product(tmp).select{|a|a[0] < a[1]}.each do |(a,b)|
  arr << (a*b) % 2019
end
p arr.min


Measured memory_bytes: 241788
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 200005
#define INF 1000000005
#define INFLL (long long)1e18
#define PI 3.1415926535897
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;
int main(){
    int n,q;
    cin>>n;
    map<int,int>m;
    ll sum=0;
    REP(i,n){
        int a;
        cin>>a;
        sum+=a;
        m[a]++;
    }
    cin>>q;
    vector<P>a(q);
    REP(i,q){
        cin>>a[i].first>>a[i].second;
    }
    REP(i,q){
        int x=m[a[i].first];
        m[a[i].first]=0;
        m[a[i].second]+=x;
        sum+=(a[i].second-a[i].first)*x;
        OUT(sum);
    }
    return 0;
}


Measured memory_bytes: 8300
N, M = map(int, input().split())

red = [True] + [False] * (N - 1)
total = [1] + [1] * (N - 1)
ans = 1
for i in range(M):
    xi, yi = map(int, input().split())
    if red[xi - 1]:
        red[yi - 1] = True
    total[xi - 1] -= 1
    total[yi - 1] += 1
    if total[xi - 1] == 0:
        red[xi - 1] = False
print(red.count(True))


Measured memory_bytes: 5348
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, s = 0ll, ans = 0;
  scanf("%lld", &n);
  ll a[n];
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a[i]);
    s ^= a[i];
  }
  for(i = 40; i >= 0; --i) {
    ll t = 1ll << i, b = (1 << (i + 1)) - 1;
    if(s & t) {
      for(j = 0; j < n; ++j) {
        if((b & a[j]) == t) {
          ans++;
          break;
        }
      }
      if(j == n) {
        printf("-1");
        return 0;
      }
      s = ~s;
    }
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 896
def main():
    n = int(input())
    A, B = [], []
    for _ in range(n):
        a, b = list(map(int, input().split()))
        A.append(a)
        B.append(b)
    ans = 0
    for a, b in zip(A[::-1], B[::-1]):
        aa = a + ans
        r = aa % b
        if r != 0:
            ans += b - r
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

#define uint unsigned int
#define llong long long int
#define ullong unsigned long long int
#define rep(i, n) for (int i = 0; i < n; ++i)

const static llong MOD = 1000000000 + 7;

template<typename T> T factorial_mod(T n) {
    if (n == 0) return 1;
    llong ret = n;
    for (int i = n - 1; i > 0; --i) {
        ret = (ret * i) % MOD;
    }

    return ret;
}

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    llong n, m;
    cin >> n >> m;
    llong big = max(n, m), small = min(n, m);
    llong ans;
    if (big - small == 1) {
        ans = (factorial_mod(big) * factorial_mod(small)) % MOD;
    } else if (big - small == 0) {
       ans = (2 * factorial_mod(big) * factorial_mod(small)) % MOD;
    } else {
        ans = 0;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

int main() {
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> A;
  for (int i = 0; i < M; i++) { int tmp; cin >> tmp; A.push_back(tmp); }
  
  int costL = 0, costR = 0;
  for (int i = 0; i < M; i++) {
    if (A[i] < X) costL++;
    else costR++;
  }
  cout << min(costL, costR) << endl;
}


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

int main()
{
    int h;
    cin >> h;
    int w;
    cin >> w;
    vector<string> a(h);
    for (int i = 0; i < h; i++)
    {
        cin >> a[i];
    }

    vector<bool> row(h, false);
    vector<bool> col(w, false);
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (a[i][j] == '#')
            {
                row[i] = true;
                col[j] = true;
            }
        }
    }

    for (int i = 0; i < h; i++)
    {
        if (row[i])
        {
            for (int j = 0; j < w; j++)
            {
                if (col[j])
                {
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }
}


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

using namespace std;

long long int N;
string S;
map<string, long long int>mp;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> S;
		mp[S]++;
	}
	if (mp.size() == 3) {
		cout << "Three" << endl;
	}
	else {
		cout << "Four" << endl;
	}
	return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = 0;
    if (a + b >= c - 1) {
        ans = b + c;
    } else  {
        ans = a + b + b;
        if (b != 0 || c != 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int N = sc.nextInt();
        int K = sc.nextInt();


        long count = 0;
        for (int a = 1; a < N + 1; a++) {
            int modA = (a % K);  // aの余り
            int modB = K - modA; // a + bはKで割り切れる必要があるので bの余りはK-(aの余り)
            int modC = K - modA; // a + cはKで割り切れる必要があるので cの余りはK-(aの余り)

            if ((modB + modC) % K == 0) { // b + cもKで割り切れる必要がある
                // N以下でKで割るとmodBになるBの個数 x N以下でKで割るとmodCになるCの個数
                long b = ((N + K - modB) / K);
                long c = ((N + K - modC) / K);
                long num = b * c;
                count += num;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 23508
void main() {
	(ri / 3).writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


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

using namespace std;

int main(void){
    int A,B;
    cin>>A>>B;
    if(A>=13){
        cout<<B<<endl;
    }else if(6<=A){
        cout<<B/2<<endl;
    }else{
        cout<<0<<endl;
    }
    return 0;
}

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

vector <string> a, cur;
int n, m;

int visited[110][110];
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

void floodfill(int i, int j, char c, char d){
    if(i < 0 || j < 0 || i >= 42 || j >= 42 || cur[i][j] != c) return;
    cur[i][j] = d;
    visited[i][j] = 1;
    for(int k=0; k<4; k++){
        floodfill(i+dr[k], j+dc[k], c, d);
    }
}
pair<int, int> check(){
    memset(visited, 0, sizeof visited);
    int cnt1 = 0, cnt2 = 0;
    cur = a;
    for(int i=0; i<42; i++){
        for(int j=0; j<42; j++){
            if(!visited[i][j]) {
                if(a[i][j] == '.') cnt1++;
                else cnt2++;
                floodfill(i, j, a[i][j], '*');
            }
        }
    }
    return {cnt1, cnt2};
}

void solve(){
    bool flag = false;
    for(int i=0; i<42 && !flag; i++){
        for(int j=0; j<42; j++){
            auto el = check();
            if(el.first == n && el.second == m){
                flag = true; break;
            }
            if(a[i][j] == '.'){
                a[i][j] = '#';
                auto el2 = check();
                if(abs(el2.first - n) + abs(el2.second - m) < abs(el.first - n) + abs(el.second - m)) ;
                else a[i][j] = '.';
            }else{
                a[i][j] = '.';
                auto el2 = check();
                if(abs(el2.first - n) + abs(el2.second - m) < abs(el.first - n) + abs(el.second - m)) ;
                else a[i][j] = '#';
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  //  freopen("in.txt", "r", stdin);
  //  freopen("out.txt", "w", stdout);
    cin >> n >> m;
    a.resize(42);
    for(int i=0; i<42; i++) a[i].resize(42);
    for(int i=0; i<42; i++){
        for(int j=0; j<42; j++){
            if((i+j) % 2) a[i][j] = '#';
            else a[i][j] = '.';
        }
    }
    int cnt = 0;
    while(true){
        auto el = check();
        cnt++;
        //cout << el.first << " " << el.second << endl;
        if(el.first == n && el.second == m) break;
        if(cnt == 3) {
            for(int i=0; i<42; i++){
                for(int j=0; j<42; j++){
                    a[i][j] = '.';
                }
            }
        }else if(cnt == 5){

            for(int i=0; i<42; i++){
                for(int j=0; j<42; j++){
                    if((i) % 2) a[i][j] = '#';
                    else a[i][j] = '.';
                }
            }
        }else if(cnt == 7){
            for(int i=0; i<42; i++){
                for(int j=0; j<42; j++){
                    if((i*j) % 2) a[i][j] = '#';
                    else a[i][j] = '.';
                }
            }
        }
        solve();
    }

    cout << 42 << " " << 42 << "\n";
    for(int i=0; i<42; i++) {
        cout << a[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 512
N = int(input())
W = [input() for i in range(N)]
a = set()
b = W[0][0] 
OK = True
for w in W:
    if b[-1]!=w[0] or w in a:
        OK = False
    a.add(w)
    b = w
print('Yes' if OK else 'No')


Measured memory_bytes: 38512
#include<bits/stdc++.h>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
#define ll long long
#define pii pair <int, int>
#define pll pair <long long, long long>
#define plxy pair <long long, pll>
#define INT_MAX 1e18
using namespace std;
using namespace std;
const int mod=1e9+7;
const int N=1e3+5;
ll a[N][N];
// return the required digit in the number
ll solve(ll x)
{
    while(x)
    {
        if(x/10==0)
            return x;
        x/=10;
    }
}
int main()
{
    ll n,ans=0;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        a[i%10][solve(i)]++;
    }
    for(ll i=1;i<=9;i++)
    {
        for(ll j=1;j<=9;j++)
        {
            ans+=a[i][j]*a[j][i];
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int i, j;
  int row, column;
  cin >> row >> column;
  
  for(i=0; i<row+2; i++){
  	if (i == 0 || i == row+1){
    	for (j=0; j<column+2; j++){
        cout << '#';
        }
    }else{
    	for (j=0; j<column+2; j++){
          	vector<char> pic(column+2);
        	if (j == 0 || j == column+1){
            	cout << '#';
            }else{
            	cin >> pic.at(j);
              	cout << pic.at(j);
            }
        }
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int n = Integer.parseInt(st.nextToken());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      
      int answer = Math.min(n*a,b);
      out.println(answer);

      
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 21332
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    INF = 10**19

    dp = [INF] * N
    dp[0] = 0

    for i in range(1, N):
        cost = INF
        for k in range(1, K + 1):
            if k > i:
                break
            cost = min(cost, dp[i - k] + abs(h[i] - h[i - k]))
        dp[i] = cost

    print(dp[-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 91052
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[N][N];
int color[N], d[N], f[N], tt;

void dfs_visit(int u) {
    int v;
    color[u] = GRAY;
    d[u] = ++tt;
    for ( v = 0; v < n; v++ ) {
    if ( M[u][v] == 0 ) continue;
    if ( color[v] == WHITE ) {
        dfs_visit(v);
    }
    }
    color[u] = BLACK;
    f[u] = ++tt;

}

void dfs() {
    int u;

    for ( u = 0; u < n; u++ ) color[u] = WHITE; tt = 0;
    for ( u = 0; u < n; u++ ) {
        if ( color[u] == WHITE ) dfs_visit(u);
    }
    for ( u = 0; u < n; u++ ) {
        printf("%d %d %d\n", u + 1, d[u], f[u]);
    }
    }



int main() {
    int u, v, k, i, j;
    scanf("%d", &n);
    for ( i = 0; i <n; i++){
        for ( j = 0; j<n; j++){
                   M[i][j] = 0;
        }
    }
        for ( i = 0; i < n; i++){
            scanf("%d %d", &u, &k);
            u--;
            for(j=0;j < k; j++){
            scanf("%d", &v);
                v--;
                M[u][v] = 1;
            }
        }
        dfs();
        return 0;
    }



Measured memory_bytes: 2108
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n; cin >> n;
  long long a, b; cin >> a >> b;
  long long res = 0;
  long long last; cin >> last;
  for (int i = 1; i < n; i++) {
  	long long t; cin >> t;
    res += min((t - last) * a, b);
    last = t;
  }
  cout << res << endl;
}

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

#define gc() getchar()

#define ll long long

using std::max;

inline int read()
{
	int ret=0;char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))
	{
		ret=ret*10+ch-'0';
		ch=gc();
	}
	return ret;
}

int main()
{
//	freopen("in.in","r",stdin);
	ll a,b,c,d;
	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
	printf("%lld\n",max(a*c,max(a*d,max(b*c,b*d))));
	return 0;
}

Measured memory_bytes: 3864
a, b = map(int, input().split())
# masu = ['#' for _ in range(10000)]
masu = [['#' for _ in range(100)] for _ in range(100)]
for i in range(50, 100):
    for j in range(100):
        masu[i][j] = '.'
cnta = 0
for i in range(0, 50):
    for j in range(99):
        if cnta < a-1 and j % 3 == 1:
            masu[i][j+i % 2] = '.'
            cnta += 1
cntb = 0
for i in range(51, 100):
    for j in range(99):
        if cntb < b-1 and j % 3 == 1:
            masu[i][j+i % 2] = '#'
            cntb += 1

print('100 100')
for i in range(100):
    for j in range(100):
        print(masu[i][j], end='')
    print('')


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

bool TxF(int x)
{
    if (x <= 1)
        return false;

    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
            return true;
}

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

    while (!TxF(X)>0)
    {
        X ++;
    }
    
cout << X <<endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
 
using namespace std;
 
 
int main(){
  int n,le,ri,mi,st,ed;
  string s;
  while(cin >> n && n){
    int L,D,M,okL,okD,okM;
    L=D=M=okL=okD=okM=0;
    st = 0;
    cin.ignore();
    for(int i=0;i<n;i++){
      getline(cin,s,'\n');
      st = s[0]=='0'?1:0;
      le = (atoi)(s.substr(st,st==0?2:1).c_str());
      st = s[3] == '0'?4:3;
      ri = (atoi)(s.substr(st,st==3?2:1).c_str());
      st = s[6]=='0'?7:6;
      mi = (atoi)(s.substr(st,st==6?2:1).c_str());
      //cout << le << " " << ri << " " << mi << endl;
      int time = le*60+ri;
      if(660 <= time && time<=899){
    L++;
    if(ri <= mi){
      if(mi-ri <= 8)okL++;
    }
    else{
      if(60-ri+mi <= 8)okL++;
    }
      }
      else if(1080<=time &&time <=1259){
    D++;
    if(ri <= mi){
      if(mi-ri <= 8)okD++;
    }
    else{
      if(60-ri+mi <= 8)okD++;
    }
 
      }else if((1260<=time && time<=1439) || (0<=time && time<= 119) ){
    M++;
    if(ri <= mi){
      if(mi-ri <= 8)okM++;
    }
    else{
      if(60-ri+mi <= 8)okM++;
    }
      }
    }
    
    cout << "lunch ";
    L==0?cout <<"no guest"<<endl:cout <<(int)(((double)okL/(double)L)*100) << endl;
    cout << "dinner ";
    D==0?cout << "no guest"<<endl:cout << (int)(((double)okD/(double)D)*100) << endl;
    cout << "midnight ";
    M==0?cout <<"no guest" << endl:cout << (int)(((double)okM/(double)M)*100) << endl;
 
  }
  return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int N;
int A[101][101];

int main(){
    std::cin >> N;
    
    FOR(i, 1, N+1){
        FOR(j, 1, N+1){
            std::cin >> A[i][j];
        }
    }

    FOR(i, 1, N+1){
        FOR(j, 1, N+1){
            A[i][j] += A[i][j-1];
        }
    }

    FOR(i, 1, N+1){
        FOR(j, 1, N+1){
            A[i][j] += A[i-1][j];
        }
    }

    // FOR(i, 1, N+1){
    //     FOR(j, 1, N+1){
    //         printf("%d, ", A[i][j]);
    //     }
    //     puts("");
    // }

    int res = -INF;
    FOR(lx, 1, N+1){
        FOR(rx, lx, N+1){
            FOR(ly, 1, N+1){
                FOR(ry, ly, N+1){
                    res = std::max(res, A[ry][rx] - A[ly-1][rx] - A[ry][lx-1] + A[ly-1][lx-1]);
                }
            }
        }
    }

    std::cout << res << std::endl;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  int N; cin >> N;
  vector<ll> A(N);
  for(auto& i : A) cin >> i;
  ll sum{};

  // -, +, -, +, ...
  ll res0{};
  for (int i = 0; i < N; ++i) {
    sum += A[i];
    if (i % 2 == 0) {
      if (sum >= 0) {
        res0 += sum - (-1);
        sum = -1;
      }
    } else {
      if (sum <= 0) {
        res0 += 1 - sum;
        sum = 1;
      }
    }
  }

  // +, -, +, ...
  sum = 0;
  ll res1{};
  for (int i = 0; i < N; ++i) {
    sum += A[i];
    if (i % 2 != 0) {
      if (sum >= 0) {
        res1 += sum - (-1);
        sum = -1;
      }
    } else {
      if (sum <= 0) {
        res1 += 1 - sum;
        sum = 1;
      }
    }
  }

  auto ans = std::min(res0, res1);
  cout << ans << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 1024
def main():
    buf = input()
    buflist = list(buf.split())
    N = int(buflist[0])
    K = int(buflist[1])
    buf = input()
    S = list(buf)
    S[K-1] = S[K-1].lower()
    print(''.join(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.io.*;
import java.util.*;


class Main {
    static final long MOD=1000000007;
    static final int N=401;
    static long[][] tbl;
    static void init(){
        tbl=new long[N][N];
        for(int i=0;i<N;++i){
            tbl[0][i]=1;
            for(int j=1;j<N;++j)
                tbl[j][i]=tbl[j-1][i]*i%MOD;
        }
        for(int i=0;i<N;++i)
            for(int j=1;j<N;++j)
                tbl[i][j]=(tbl[i][j]+tbl[i][j-1])%MOD;
    }
    static long f(int a,int b,int d){
        return (tbl[d][b]-tbl[d][a-1]+MOD)%MOD;
    }
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        init();
        int n=sc.nextInt();
        int c=sc.nextInt();
        int[]a=new int[n],b=new int[n];
        for(int i=0;i<n;++i)a[i]=sc.nextInt();
        for(int i=0;i<n;++i)b[i]=sc.nextInt();
        long[][]dp=new long[n+1][c+1];
        dp[0][0]=1;
        for(int i=0;i<n;++i){
            for(int j=0;j<=c;++j){
                for(int k=0;k<=j;++k){
                    dp[i+1][j]+=dp[i][j-k]*f(a[i],b[i],k);
                    dp[i+1][j]%=MOD;
                }
            }
        }
        out.println(dp[n][c]);
        out.close();
    }
    // http://codeforces.com/blog/entry/7018
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 27732
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n, m;
  cin >> n >> m;
  int total = m * 1900 + (n - m) * 100;
  double baseP = pow(0.5, m);
  double p     = baseP;
  double hoP   = 0;
  double ans = 0;
  rep (i, 1000) {
    ans += (i + 1) * total * p;
    // cout << p << " => " << ans << endl;
    hoP = hoP + p;
    p = (1 - hoP) * baseP;
  }
  P(ans);

  return 0;
}





Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
int digs[5];
char c[5];
string str;

bool comp(const int &a, const int &b) {
    return a > b;
}

int sortDigit(int num) {
    int idx = 0;
    while (num != 0) {
        digs[idx++] = num % 10;
        num /= 10;
    }
    sort(digs, digs+idx, comp);
    int sdigit = 0, p = 1;
    for (int i = idx-1; i >= 0; i--) {
        sdigit += p * digs[i];
        p*=10;
    }
    while (sdigit < 1000) sdigit *= 10;
    return sdigit;
}

int revNum(int num) {
    int revnum = 0;
    while (num != 0) {
        revnum = revnum * 10 + (num % 10);
        num /= 10;
    }
    return revnum;
}

bool isSameDig(int num) {
    int dig = num % 10;
    num /= 10;
    while (num != 0) {
        if (dig != num % 10) return false;
        num /= 10;
    }
    return true;
}

int main(){
    int base = 6174;
    int prev, L, S, steps = 0;
    for (; ;) {
        scanf("%d", &prev);
        if (prev == 0) break;
        steps = 0;
        bool flag = false;
        while (prev != base) {
            L = sortDigit(prev); S = revNum(L);
            if (isSameDig(L)) { flag = true; break; }
            prev = L - S;
            steps++;
        }
        if (!flag) printf("%d\n", steps);
        else printf("NA\n");
    }
    return 0;
}



Measured memory_bytes: 2704
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		for(int i = 0; i < n; i++){
			String[] s = sc.nextLine().split(" ");
			xyr(s);
		}
		sc.close();
	}
	static void xyr(String[] s){
		double x, y, r;
		double[] xi = new double[3];
		double[] yi = new double[3];
		for(int i = 0; i < 3; i++){
			xi[i] = Double.parseDouble(s[2*i]);
			yi[i] = Double.parseDouble(s[2*i+1]);
		}
		x = xp(xi, yi);
		y = xp(yi, xi);
		r = Math.pow(((xi[1]-x)*(xi[1]-x)+(yi[1]-y)*(yi[1]-y)), 0.5);
		System.out.println(String.format("%.3f %.3f %.3f", x, y, r));
	}
	static double xp(double[] x, double[] y){
		return ((x[1]*x[1]+y[1]*y[1])*(y[0]-y[2])+(x[2]*x[2]+y[2]*y[2])*(y[1]-y[0])+(x[0]*x[0]+y[0]*y[0])*(y[2]-y[1]))/(2*(x[2]*y[1]-x[1]*y[2]+x[0]*y[2]-x[2]*y[0]+x[1]*y[0]-x[0]*y[1]));
	}
}

Measured memory_bytes: 12000
import sys
s=input()
if(s[0]!="A"):
    print("WA")
    sys.exit(0)
if(s[1].isupper()):
    print("WA")
    sys.exit(0)
flag=0
for i in range(2,len(s)-1):
    if(s[i].isupper()):
        flag+=1
        if(flag>=2 or s[i]!="C"):
            print("WA")
            sys.exit(0)
if(s[len(s)-1].isupper() or flag!=1):
    print("WA")
else:
    print("AC")

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <string.h>
#include <climits>

using namespace std;

int ar[10000];

int main() {
    int n;
    cin >> n;
    for(int i=0; i<2*n; i++ ) {
        cin >> ar[i];
    }
    sort(ar, ar+(2*n));
    int res = 0;
    for(int i=0; i<2*n; i+=2) {
        res += ar[i];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256