akhauriyash/Code-Regression huggingface dataset:
n, m = [int(x) for x in raw_input().split()]
a = []
al, ar = 1, n
for _ in xrange(m):
    l, r = [int(x) for x in raw_input().split()]
    a.append((l, r))
a.sort()
for (l, r) in a:
    al = max(l, al)
    ar = min(r, ar)
ans = max(ar - al + 1, 0)
print ans


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

int main(){
    int n,down = 0,count = 0;
    cin >> n;
    vector<long long>a(n),b(n),margin;
    long long a_all = 0,b_all = 0,shotage = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        a_all += a[i];
    }
    for(int i = 0;i < n;i++){
        cin >> b[i];
        b_all += b[i];
    }

    if(b_all > a_all){
        cout << -1 << endl;
        return 0;
    }
    for(int i = 0;i < n;i++){
        if(a[i] < b[i])shotage += b[i] - a[i],down++;
        else if(a[i] > b[i])margin.push_back(a[i] - b[i]);
    }
    sort(margin.begin(),margin.end(),greater<long long>());

    for(int i = 0;i < (int)margin.size();i++){
        if(shotage <= 0)break;
        shotage -= margin[i];
        count++;
    }
    cout << down + count << endl;
}


Measured memory_bytes: 2428
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
#define rep(i,a,b) for(int (i)=int(a);(i)<int(b);(i)++)
#define rrep(i,a,b) for(int (i)=int(a);(i)>=int(b);(i)--)

#define put(a) cout << (a) << endl
#define puts(a) cout << (a) << " "

#define llint long long int

#define INF (long long)1e9+1
#define MOD (long long)1e9+7
#define INF64 (long long)1e18+1

#define F first
#define S second

#define Pii  pair<int,int>
#define Pll  pair<long long,long long>
#define Piii pair<int,pair<int,int>>
#define Plll pair<long long,pair<long long,long long>>

#define Vll(a,b,c)    vector<vector<long long>> (a)((b),vector<long long>((c))
#define Vlll(a,b,c,d) vector<vector<vector<long long>>> (a)((b),vector<vector<long long>>((c),vector<long long>((d)))

#define MAX_N 1000000

int main (void)
{
  //INPUT
  llint N,K;
  cin >> N >> K;
  vector<llint> A(N);
  rep(i,0,N) {
    cin >> A[i];
  }

  //SOLVE
  llint ans=0;
  llint bufr,bufl;
  llint bufk,bufk2;
  bufk = (K*(K+1)/2)%(MOD);
  bufk2 = (K*(K-1)/2)%(MOD);
  llint left_no,right_no;
  rep(i,0,N) {
    left_no = 0;
    right_no = 0;
    for(int k=0;k<i;k++) {
      if (A[i] > A[k]) {
        left_no++;
      }
    }
    for(int k=i+1;k<N;k++) {
      if (A[i] > A[k]) {
        right_no++;
      }
    }

    bufr = (right_no*bufk) % (MOD);
    bufl = (left_no*bufk2) % (MOD);
    ans = (ans + bufr + bufl)%(MOD);

  }

  //OUTPUT
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var A, B int
	fmt.Scan(&A, &B)

	fmt.Println(max(A+B, A-B, A*B))
	return

}

func max(nums ...int) int {
	res := math.MinInt32
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return int(res)
}


Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int k,a,b,i;
    scanf("%d%d%d",&k,&a,&b);
    for(i=a;;i++)
    {
        if(i>b)
        {
            printf("NG");
            break;
        }
        else if(i%k==0)
        {
            printf("OK");
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1736
//
// Created on 2019/12/05.
//

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(x) x.begin(),x.end()
#define DEBUG

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    int ans = 1;
    int heightMax = h[0];
    rep(i,n-1)
    {
        if(h[i+1] >= heightMax)
        {
            ++ans;
            heightMax = h[i+1];
        }
    }

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

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int xx = 0, yy = 0;

        while(y != 0){
        if(x <= y){
            int t = x;
            x = y;
            y = t;
        }

        xx = y;
        yy = x % y;

        x = xx;
        y = yy;
        }
        
        System.out.println(xx);

        sc.close();
    }
}


Measured memory_bytes: 26404
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int INF=1e5;

int main(){
	int n;
	cin>>n;
	string S[50];
	rep(i,n)cin>>S[i];
	int ch[26];
	rep(j,26)ch[j]=INF;
	rep(i,n){
		int pat[26];
      	rep(j,26)pat[j]=0;
		int l=(int)S[i].length();
		rep(j,l){
			char x=S[i][j];
			int d=x-'a';
			pat[d]++;
		}
		rep(j,26)ch[j]=min(ch[j],pat[j]);
	}
	rep(j,26)rep(i,ch[j]){char p='a'+j;cout<<p;}
}

Measured memory_bytes: 256
//ABC 162 C
#include <iostream>
using namespace std;

int fact(int a,int b){
    int i,ii,kazu,kazuzu,ireka;
    if(a < b){
        ireka = a;
        a = b;
        b = ireka;
    }
    if(a > b){
        while(i == 0){
            kazu = a / b;
            if(b * kazu == a){
                i = 1;
            }else{
                kazuzu = a;
                a = b;
                b = kazuzu - kazu * b;
            }
        }
        return(b);
    }else if(a == b){
        return(a);
    }
}
int gcd(int a,int b){
    if(a % b == 0){
        return(b);
    }else{
        return gcd(b , a % b);
    }

}
int main(){
    long long int a,b,c,d;
    b = c = d = 0;
    cin >> a;
    for(int i = 1;i <= a;i++){
        for(int ii = 1;ii <= a;ii++){
            for(int iii = 1;iii <= a;iii++){
                b = gcd(i,ii);
                c = gcd(b,iii);
                d = d + c;
            }
        }
    }
    cout << d << endl;


}

Measured memory_bytes: 3580
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
typedef pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

const int MAX_E = 1e5 + 1;
int N;
int par[MAX_E];
int UFTrank[MAX_E];

void init(int n) {
   for (int i = 0; i < n; i++) {
      par[i] = i;
      UFTrank[i] = 0;
   }
}

int find(int x) {
   if (par[x] == x) {
      return x;
   } else {
      return par[x] = find(par[x]);
   }
}

void unite(int x, int y) {
   x = find(x);
   y = find(y);
   if (x == y) return;

   if (UFTrank[x] < UFTrank[y]) {
      par[x] = y;
   } else {
      par[y] = x;
      if (UFTrank[x] == UFTrank[y]) UFTrank[x]++;
   }
}

bool same(int x, int y) {
   return find(x) == find(y);
}       

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
   return e1.cost < e2.cost;
}

edge es[MAX_E * 2];

int main() {
   int V, E;
   cin >> V >> E;
   int s, t, w;
   for (int i = 0; i < E; i++) {
      cin >> s >> t >> w;
      es[i].u = s;
      es[i].v = t;
      es[i].cost = w;
   }
   sort(es, es + E, comp);
   init(V);
   int ans = 0;
   for (int i = 0; i < E; i++) {
      edge e = es[i];
      if (!same(e.u, e.v)) {
         unite(e.u, e.v);
         ans += e.cost;
      }
   }

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



Measured memory_bytes: 4360
import scala.io.StdIn.readInt

object Main {
  val c = Math.cos(Math.PI/3)
  val s = Math.sin(Math.PI/3)
  def main(args:Array[String]) = {
    val n = readInt
    var list = IndexedSeq(((0D,0D),(100D,0D)))
    (1 to n).foreach { _=>
      list = for{
        i<-list;
        p1 = (i._1._1*2/3+i._2._1/3,i._1._2*2/3+i._2._2/3)
        p2 = (i._1._1/3+i._2._1*2/3,i._1._2/3+i._2._2*2/3)
        x = (p2._1-p1._1)*c-(p2._2-p1._2)*s+p1._1
        y = (p2._1-p1._1)*s+(p2._2-p1._2)*c+p1._2
        p3 = (x,y)
        j<-List((i._1,p1),(p1,p3),(p3,p2),(p2,i._2))
      } yield j
    }

    for(i<-list)
      printf("%.8f %.8f\n",i._1._1,i._1._2)
    printf("%.8f %.8f\n",list.last._2._1,list.last._2._2)
  }
}

Measured memory_bytes: 59188
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll MOD = 1000000000 + 7;

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

	int x = 0;
	string t = "x";
	for (int i = 0; i < s.length(); i++)
	{
		if (s.substr(i, 1) != t)
		{
			x++;
		}
		t = s.substr(i, 1);
	}

	cout << x - 1 << endl;
}

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

#include <cstdlib>  // abs() for integer 絶対値求めやつ

#include <cmath>    // abs() for float, and fabs()

#include <algorithm>
#include <vector>
#define rep(i,n) for(int i = 0; i< (n);i++)

#define SORT(a) sort((a).begin(),(a).end());

#define che(a,string) cout<<string<<":"<<(a)<<endl;

#define ch(a,string) cout<<string<<":"<<(a)<<" ";

using namespace std;

typedef pair<int,int> P;

int main(){
	long long n ; cin>>n;
	if(0==n%2){
		cout << n << endl;
	  }
	  else{
		  cout << 2 * n <<endl;
		}
	  }



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

int main(){
    int n;
    cin >> n;
    vector<int> ans(n+1, 0);
    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            if(x*x+y*y+x*y > n) break;
            for(int z = 1; z <= n; z++){
                if(x*x+y*y+z*z+x*y+y*z+z*x <= n){
                    ans[x*x+y*y+z*z+x*y+y*z+z*x]++;
                }else{
                    break;
                }
            }
        }
    }

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

Measured memory_bytes: 3628
N=int(input())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())
X=[]
for i in range(N):
    if A[i]>B[i]:
        X.append(B[i])
if len(X)==0:
    print(0)
else:
    print(sum(A)-min(X))


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

int n;
string s;
bool check(int x,int y,vector<int> &v){
    v.push_back(x);
    v.push_back(y);
    rep(i,n-1){
        if(s[i+1] == 'o'){
            if(v[i+1] == 0)v.push_back(v[i]);
            else v.push_back(v[i]^1);
        }
        else {
            if(v[i+1] == 0)v.push_back(v[i]^1);
            else v.push_back(v[i]);
        }
        
    }
    if(s[0] == 'o'){
        if(x == 0)return (v[1] == v[n-1])&&(v[0] == v[n]);
        else return (v[1] != v[n-1])&&(v[0] == v[n]);
    }
    else{
        if(x == 0)return (v[1] != v[n-1])&&(v[0] == v[n]);
        else return (v[1] == v[n-1])&&(v[0] == v[n]);
    }
    
}

signed main(){
    cin >>n ;
    cin >> s;
    vector<int> v1,v2,v3,v4;
    string ans = "";
    if(check(0,0,v1)){
        rep(i,n){
            if(v1[i] == 0)ans += 'S';
            else ans+= 'W';
        }
        cout << ans  << endl;
        return 0;

    }
    

    if(check(0,1,v2)){
        rep(i,n){
            if(v2[i] == 0)ans+='S';
            else ans+='W';
        }
        cout << ans << endl;
        return 0;

    }
    
    if(check(1,0,v3)){
        rep(i,n){
            if(v3[i] == 0)ans += 'S';
            else ans+= 'W';
        }
        cout << ans << endl;
        return 0;

    }
    
    if(check(1,1,v4)){
        rep(i,n){
            if(v4[i] == 0)ans+= 'S';
            else ans+= 'W';
        }
        cout << ans << endl;
        return 0;

    }
    cout << -1 << endl;


    return 0;
}

Measured memory_bytes: 4340
# Your code here!

#データの読み込み

fline=readlines
input=fline[0].split(" ")

#実際の処理

a=input[0].to_i
b=input[1].to_i

ans=a+b
temp=a-b
if ans<temp then
    ans=temp
end
temp=a*b
if ans<temp then
    ans=temp
end

#出力

printf('%d', ans)





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

using namespace std;

int n;

void dfs(string s){
    if((int)s.size()==n){
        cout << s << endl;
        return;
    }
    int mx=0;
    for(int i=0;i<s.size();i++){
        mx=max(mx,(int)s[i]);
    }
    for(int i=0;i<mx-95;i++){
        dfs(s+(char)('a'+i));
    }
}

int main()
{
    cin >>n;
    dfs("a");
    return 0;
}


Measured memory_bytes: 1536
# coding: utf-8
# Your code here!
n=int(input())
s=list(input())
ans=10**10
wl=0
el=0
wr=s.count('W')
er=s.count('E')
for i in range(n):
    if wl+er<ans:
        ans=wl+er
    if s[i]=='E':
        el+=1
        er-=1
    else:
        wl+=1
        wr-=1
    if wl+er<ans:
        ans=wl+er
print(ans)


Measured memory_bytes: 5916
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define db(x) cout<<#x<<"="<<x<<endl
#define deb(x) each(x.begin(),x.end(),(int& y){cout << y <<" ";})
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define y1 y1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


void Main(){

  int N; cin>>N;

  double gu=0;
  double ki=0;

  reps(i,1,N+1){
    if(i%2==0) ++gu;
    else ++ki;
  }

  cout<< ki/N <<"\n";

}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long ll;

string n;
vector<string> parts = {"7","5","3"};
int dfs(string num){
  ll i_num;
  if(num == "") i_num = 0;
  else i_num = stoll(num);

  if(i_num > stoll(n)) return 0;
  
  map<char,int> m;
  rep(i,num.size()){
    m[num[i]]++;
  }

  int ans = (m['7'] > 0 && m['5'] > 0 && m['3'] > 0) ? 1:0;
  for(string p : parts){
    ans += dfs(num+p);
  }
  return ans;
}

int main(){
  cin >> n;
  cout << dfs("") << endl;
}


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

long long a, n, m;
long long val(long long x){
  long long sum = 0;
  while(x){
    sum += x%10;
    x /= 10;
  }
  return sum;
}

int solve(){
  int cnt = 0;
  for ( int y = 1; y <= 72; y++ ){
    long long x = 1;
    for ( int t = 1; t <= n; t++ ){
      x *= (y+a);
    }
    if (x <= m && val(x) == y) cnt++;
  }
  return cnt;
}

int main() {
  cin >> a >> n >> m;
  cout << solve() << endl;
}  


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


int main() {

  stack<int> S1; // 地形描画用スタック
  stack<pair<int, int> > S2; // 総面積用スタック
  char ch;
  int sum;
  for (int i=0; cin >> ch; i++) {
    if (ch == '\\') S1.push(i);
    else if (ch == '/' && S1.size() > 0 ) {
      int j = S1.top();
      S1.pop();
      sum += i - j;
      int a = i - j;
      while (S2.size() > 0 && S2.top().first > j) {
        a += S2.top().second;
        S2.pop();
      }
      S2.push(make_pair(j, a));
    }
  }

  vector<int> ans;
  while (S2.size() > 0) {
    ans.push_back(S2.top().second);
    S2.pop();
  }

  reverse(ans.begin(), ans.end());
  cout << sum << endl;
  cout << ans.size();
  rep(i, ans.size()) {
    cout << " ";
    cout << ans[i];
  } 
  cout << endl;

  return 0;
}


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

int main(){
 int N;
  string S;
  cin>>N>>S;
  int a=(int)S.size();
  if(a<=N){
    cout<<S<<endl;
  }else{
    for(int i=0;i<N;i++){
      cout<<S.at(i);
    }
    cout<<"..."<<endl;
  }
}

Measured memory_bytes: 3632
s = input()

for i in range(int(input())):
    cmd = input().split()
    a, b = int(cmd[1]), int(cmd[2])

    if cmd[0] == 'print':
        print(s[a:b+1])
    elif cmd[0] == 'reverse':
        s = s[:a] + s[a:b+1][::-1] + s[b+1:]
    elif cmd[0] == 'replace':
        s = s[:a] + cmd[3] + s[b+1:]

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int INF=1e9;
const ll MOD=1e9+7;
template<typename A,size_t N,typename T>
void Fill(A (&array)[N],const T &val)
{
    std::fill( (T*)array,(T*)(array+N),val );
}

int main(void)
{
    ll A[300005];
    int N;
    cin >> N;
    ll ans=0;
    for(int i=0;i<N;i++)
    {
        cin >> A[i];
    }
    ll onenum=0;
    ll zeronum=0;
    ll tmp=0;
    for(ll j=0;j<60;j++)
    {
        onenum=0;
        zeronum=0;
        for(int i=0;i<N;i++)
        {
            if(A[i]&(1LL<<j)) onenum++;
        }
        zeronum=N-onenum;
        tmp=(1LL<<j)%MOD;
        tmp=(tmp*onenum)%MOD;
        tmp=(tmp*zeronum)%MOD;
        ans=(ans+tmp)%MOD;
    }
    cout << ans << endl;

}

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

int main() {
  int N, K; cin >> N >> K;
  vector<long long> V(N);
  for (int i = 0; i < N; i++) cin >> V[i];

  long long res = 0;

  for (int p = 0; p <= min(K, N); p++) {
    for (int q = 0; p + q <= min(K, N); q++) {
      vector<long long> v;
      long long cur = 0;
      for (int i = 0; i < p; i++) {
        v.push_back(V[i]), cur += V[i];
      }
      for (int i = 0; i < q; i++) {
        v.push_back(V[N-1-i]), cur += V[N-1-i];
      }

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

      for (int i = 0; i < min(K - p - q, (int)v.size()); i++) {
        if (v[i] < 0) cur -= v[i];
      }

      res = max(res, cur);
    }
  }

  cout << res << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
int n,m,a[5200],b[5200];
vector<int> ga[2600],rg[2600];
bool v1[2600],v2[2600];
long long p,c[5200];
struct Bellman_Ford_Algorithm{
	int V,E;
	vector<pair<pair<int,int>,long long> > Edges;
	vector<long long> dist;
	Bellman_Ford_Algorithm(int vv=0){
		V=vv;
		dist.resize(vv+1,1e18);
		E=0;
		Edges.resize(0);
	}
	void AddEdge(int u,int v,long long w){
		E++;
		Edges.push_back(make_pair(make_pair(u,v),w));
	}
	bool ShortestPath(int src=1){
		dist[src]=0;
		bool upd;
		for(int i=1;i<=10000;i++){
			upd=false;
			for(int j=0;j<E;j++){
				if(dist[Edges[j].first.first]+Edges[j].second<dist[Edges[j].first.second]){
					dist[Edges[j].first.second]=dist[Edges[j].first.first]+Edges[j].second;
					upd=true;
				}
			}
			if(upd&&i==10000){
				return 1;
			}
		}
		return 0;
	}
}bfa;
void s1(int u){
	v1[u]=true;
	for(int v:ga[u]) if(!v1[v]) s1(v);
}
void s2(int u){
	v2[u]=true;
	for(int v:rg[u]) if(!v2[v]) s2(v);
}
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>p;
	bfa=Bellman_Ford_Algorithm(n);
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i];
		c[i]=p-c[i];
		ga[a[i]].push_back(b[i]);
		rg[b[i]].push_back(a[i]);
	}
	s1(1);s2(n);
	for(int i=1;i<=m;i++)
		if(v1[a[i]]&&v1[b[i]]&&v2[a[i]]&&v2[b[i]])
			bfa.AddEdge(a[i],b[i],c[i]);
	bool cir=bfa.ShortestPath();
	if(cir) cout<<"-1"<<endl;
	else cout<<max(-bfa.dist[n],0LL)<<endl;
	return 0;
}


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



namespace Test
{
    class MainClass
    {
        static void Main(string[] args) {
            int n = int.Parse(Console.ReadLine());
            var s = Console.ReadLine().Split(' ');
            var a = new int[100];
            int maxval = -1;
            int minval = 1000000001;
            for (int i = 0; i < n; i++) {
                a[i] = int.Parse(s[i]);
                maxval = Math.Max(maxval, a[i]);
                minval = Math.Min(minval, a[i]);
            }
            Console.WriteLine(maxval - minval);
        }
    }
}


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

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 1000000007ll;

int n;
int k;
int a[25];

ll comb[1252][1252];
ll dp[25][1252];    // dp[i][j] := i日見た 残りj人

ll modpow(ll a, ll b){
    ll r = 1;
    while(b){
        if(b&1)r=r*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return r;
}
ll modinv(ll a){
    return modpow(a, MOD-2);
}
ll invcombn[1252];

int main(){
    scanf("%d%d",&n,&k);
    REP(i,k)scanf("%d",a+i);

    REP(i,1252)REP(j,1252){
        if(j==0 || j==i){
            comb[i][j] = 1;
        }else if(j>i){
            comb[i][j] = 0;
        }else{
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
        }
    }
    // REP(i,10){
    //     REP(j,10)printf("%lld ",comb[i][j]);puts("");
    // }
    REP(i,1252)invcombn[i] = modinv(comb[n][i]);

    dp[0][n] = 1;
    REP(i,k){
        REP(j,n+1)if(dp[i][j]){
            REP(y,min(j,a[i])+1){
                ll add = dp[i][j];
                add = add * comb[j][y] % MOD;
                add = add * comb[n-y][a[i]-y] % MOD;
                add = add * invcombn[a[i]] % MOD;

                (dp[i+1][j-y] += add) %= MOD;
            }
        }
    }
    // REP(i,k+1){
    //     REP(j,n+1)printf("%lld ",dp[i][j]); puts("");
    // }

    ll ans = dp[k][0];
    REP(i,k)ans = ans * comb[n][a[i]] % MOD;
    printf("%lld\n",ans);
    return 0;
}


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

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int maxn = 1e6 + 1;
vector<bool> prime(maxn, true);
vector<bool> mp(maxn);


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt = 1; // cin >> t;
    for (; tt; tt--) {
    int n; cin >> n;
    vector<int> a(n);
    int GCD = 0;
    bool p_w = true;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        GCD = gcd(GCD, a[i]);
        if (a[i] == 1) continue;
        if (mp[a[i]]) p_w = false;
        mp[a[i]] = true;
    }
    if (p_w) {
        for (int i = 2; i < maxn; i++) {
            if (prime[i]) {
                int cnt = 0;
                for (int j = i; j < maxn; j+=i) {
                    prime[j] = false;
                    if (mp[j]) cnt++;
                }
                if (cnt > 1) p_w = false;
            }
        }
    }
    if (p_w) {
        cout << "pairwise coprime" << endl;
    }
    else {
        if (GCD == 1) {
            cout << "setwise coprime" << endl;
        }
        else {
            cout << "not coprime" << endl;
        }
    }
    }
    return 0;
}




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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

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

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int N, K;
vint A;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> K;
  resz(A, N);
  int GCD = 0;
  int mx = 0;
  rep(i, N) {
    cin >> A[i];
    chmax(mx, A[i]);
    if(i == 0) GCD = A[i];
    else GCD = __gcd(GCD, A[i]);
  }
  if(mx < K || K%GCD != 0) {
    cout << "IMPOSSIBLE" << endl;
  } else {
    cout << "POSSIBLE" << endl;
  }

  return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


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

  cout << (s[2]==s[3] && s[4]==s[5] ? "Yes" : "No") << endl;
}



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

using namespace std;
using ll = long long;
const ll N = 3001, mod = 1e9 + 7;

double p[ N ];
double dp[ N ][ N ];
int n;

double dfs(int pos, int k) {
    if( pos == n + 1 ) {
        return k == 0 ? 1.0 : 0.0;
    }
    double &ret = dp[ pos ][ k ];
    if( ret != -1.0 ) return ret;
    ret = 0.0;
    ret = p[ pos ] * dfs(pos + 1, k - 1);
    ret += (1.0 - p[ pos ]) * dfs(pos + 1, k);
    return ret;
}

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

    cin >> n;
    for(int i = 1; i <= n; i += 1) cin >> p[ i ];

    for(int i = 0; i <= n; i += 1)
        for(int j = 0; j <= n; j += 1)
            dp[ i ][ j ] = -1.0;

    double ans = 0.0;
    for(int i = n / 2 + 1; i <= n; i += 1)
        ans += dfs(1, i);
    cout << setprecision(10) << fixed << ans << '\n';
    return 0;
}


Measured memory_bytes: 70784
#!/usr/bin/env python3
import sys


def solve(N: int, K: int):
    # a, b <= N
    # a % b >= K
    res = 0
    for b in range(K+1, N+1):
        m, r = divmod(N, b)
        res += N + 1
        if K == 0:
            res -= 1
        res -= m * K # 0 ~ m*b-1
        res -= min(r+1, K) # m*b ~ m*b+r (=N)
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38896
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        final String S = scan.next();
        final String T = scan.next();
        scan.close();

        int count = 0;
        for (int i = 0; i < 3; i++) {
            if (S.charAt(i) == T.charAt(i)) {
                count++;
            }
        }

        System.out.println(count);
    }
}


Measured memory_bytes: 23892
#
# File    : A.rb
# Author  : Kazune Takahashi
# Created : 2018-6-16 20:47:32
# Powered by Visual Studio Code
#

a, b = gets.chomp.split(" ").map{|i| i.to_i}
# s = gets.chomp

if a <= 8 && b <= 8
  puts "Yay!"
else
  puts ":("
end

Measured memory_bytes: 1788
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
//#define int unsigned long long
#define all(x) (x).begin(), (x).end()
#define double long double

using namespace std;

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

const int MOD = 998244353;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;



int A[100010],B[100010];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N; cin >> N;
	REP(i, N+1) {
		cin >> A[i];
	}
	REP(i, N) {
		cin >> B[i];
	}
	int ans = 0;
	REP(i, N) {
		int res = min(A[i], B[i]);
		ans += res;
		B[i] -= res;
		int res2 = min(A[i + 1], B[i]);
		ans += res2;
		A[i + 1] -= res2;
	}
	print(ans);
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int main()
{
    string s;
    cin>>s;
    for(char c:s)
    {
        if(c=='7')
        {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


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

int gcd(int a, int b){
    if (b == 0) {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}

int main(){
    int N, X;
    cin >> N >> X;
    vector<int> x(N+1);
    for(int i = 0; i < N; i++)
    {
        cin >> x.at(i);
    }
    x.at(N) = X;
    sort(x.begin(), x.end());
    vector<int> dist(N);
    for(int i = 0; i < N; i++)
    {
        dist.at(i) = x.at(i+1) - x.at(i);
    }
    int ans = dist.at(0);
    for(int i = 0; i < N; i++)
    {
        ans = gcd(ans, dist.at(i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <queue>
using namespace std;

int main(){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    int len = y+z;
    int num = x/len;
    if(x%len < z) printf("%d\n",num-1);
    else printf("%d\n",num);
    return 0;
}


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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define dbg(var) {std::cout << #var << "  = " << var << nl;}
#define vi vector<int>
typedef long long ll;

using namespace std;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 

	int n , q;
	cin >> n >> q;
	
	vector<tuple<int,int,int>> w(n);
	auto getS = [](auto& e)->int& { return get<0>(e); }; 
	auto getT = [](auto& e)->int& { return get<1>(e); }; 
	auto getX = [](auto& e)->int& { return get<2>(e); };
	for(auto& el : w) cin >> getS(el) >> getT(el) >> getX(el);
	
	
	unordered_map<int, vi> blockers;
	unordered_map<int, vi> unblockers;
	
	rep(i , n)
	{
		int s = getS(w[i]);
		int t = getT(w[i]);
		int x = getX(w[i]);
		
		blockers[max(s - x , 0)].pb(x);
		//cout << "Added blocker " << x << " " << max(s - x , 0) << endl;
		unblockers[max(t - x ,0)].pb(x);
		//cout << "Added unblocker " << x << " " << max(t - x , 0) << endl;
	}
	
	vi d(q);
	for(auto& el : d) cin >> el;
	
	set<int> times;
	for(auto& el : blockers) times.insert(el.fi);
	for(auto& el : unblockers) times.insert(el.fi);
	for(auto& el : d) times.insert(el);
	times.insert(0);
	
	//cout << "Times: "; for(auto t : times) cout << t << " ";cout << nl;
	
	multiset<int> cur;
	unordered_map<int,int> blocked;
	for(auto t : times)
	{
		for(auto el : blockers[t])
			cur.insert(el);
		for(auto el : unblockers[t])
			cur.erase(cur.find(el));
		if(cur.empty())
			blocked[t] = -1;
		else
			blocked[t] = *cur.begin();
	}
	
	rep(i , q) cout << blocked[d[i]] << endl;
	
	
	return 0;
}


Measured memory_bytes: 145852
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 5e5 + 5;
const int MAXQ = 5e5 + 5;

struct BIT
{
	int tree[MAXN], n;
	#define lowbit(x) ((x)&-(x))
	inline void update(int x,int k)
	{
		while(x<=n)
			tree[x] += k,
			x += lowbit(x);
	}
	inline int query(int x)
	{
		int res=0;
		while(x)
			res += tree[x],
			x ^= lowbit(x);
		return res;
	}
	inline int query(int l,int r){ return query(r)-query(l-1);}
}bit;

int a[MAXN];

struct Query
{
	int l,r,id;
}qry[MAXQ];
inline bool cmp(const Query &p,const Query &q){ return p.r < q.r;}

int ans[MAXQ];

int main(void)
{
	int n,Q;
	scanf("%d%d",&n,&Q);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	for(int i=1; i<=Q; ++i)
		scanf("%d%d",&qry[i].l,&qry[i].r),
		qry[i].id = i;
	
	sort(qry+1,qry+Q+1,cmp);
	bit.n=n;
	
	static int lst[MAXN];
	for(int i=1, j=1; i<=n && j<=Q; ++i)
	{
		if(lst[a[i]]) bit.update(lst[a[i]], -1);
		bit.update(i, 1);
		lst[a[i]] = i;
		
		while(j<=Q && qry[j].r == i)
			ans[qry[j].id] = bit.query(qry[j].l, qry[j].r),
			++j;
	}
	
	for(int i=1; i<=Q; ++i) printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 17432
# 解説AC
mod = 10 ** 9 + 7
n, k = map(int, input().split())
dp = [-1] * (k + 1)
ans = 0
for i in range(k, 0, -1):
    dp[i] = pow(k // i, n, mod)
    t = 0
    t += 2 * i
    while t <= k:
        dp[i] -= dp[t]
        dp[i] %= mod
        t += i
    ans += i * dp[i]
    ans %= mod
print(ans)


Measured memory_bytes: 11236
import java.util.LinkedList;
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int MAX = 32768;
		
		boolean is_prime[] = new boolean[MAX + 1];
		
		for(int i = 2; i <= MAX; i++){
			is_prime[i] = true;
		}
		
		for(int i = 2; i <= Math.sqrt(MAX); i++){
			if(is_prime[i]){
				for(int j = i * 2; j <= MAX; j += i){
					is_prime[j] = false;
				}
			}
		}
		
		while(true){
			final int n = sc.nextInt();
			
			if(n == 0){
				break;
			}
			
			int count = 0;
			
			for(int i = 2; i <= n; i++){
				if(!is_prime[i]){continue;}
				
				for(int j = i; (i + j) <= n; j++){
					if(!is_prime[j] || (i + j) != n){continue;}
					
					count++;
				}
			}
			
			System.out.println(count);
		}
		
	}

}

Measured memory_bytes: 12000
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
      	int b = scan.nextInt();
      
      	if (b >= a) {
          System.out.println("unsafe");
        } else {
          System.out.println("safe");
        }
 
        scan.close();
    }
}

Measured memory_bytes: 35700
l,r=map(int,input().split())
mod=2019
cnt=0
a=[]
for i in range(l,r+1):
    cnt+=1
    a.append(i)
    if cnt>=2020:
        break
ans=10**10
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        ans=min(ans,(a[i]*a[j])%mod)

print(ans)

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

using namespace std;

regex re("A.*Z");

int main(){
    int n,m;
    cin >>n>>m;
    int ans,i;
    ans=n*(n-1)/2+m*(m-1)/2;
    
    cout<< ans << endl;
    
    
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <string>
#include <algorithm>
//#include <utility>
//#include <stack>
//#include <queue>
//#include <tuple>
//#include <set>
//#include <map>
//#include <unordered_map>
//#include <vector>
//#include <functional>
#include <bitset>
//#include <cmath>
using namespace std;

typedef long long lint;
typedef unsigned long long ulint;
#define MOD 1000000007

int main(){
    bitset<5001> B;
    int N,K;
    cin >> N >> K;
    int A[5000];
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A,A+N);

    int l=-1,u=N;
    while(u-l>1){
        int i=(l+u)/2;
        B=1;
        for(int j=0;j<N;j++){
            if(j!=i) B|=(B<<A[j]);
        }
        for(int j=K-1;j>=K-A[i];j--){
            if(j<0) break;
            if(B[j]){
                u=i;
                break;
            }
        }
        if(u!=i) l=i;
    }

    cout << (l+1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int N, M;
int A[303][303];
set<int>st;

int rec(){
	if (st.size() == 1)return N;
	vector<int>li(M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (st.count(A[i][j])) {
				li[A[i][j]]++;
				break;
			}
		}
	}
	int ma = *max_element(all(li));
	int idx = max_element(all(li))-li.begin();
	st.erase(idx);
	return min(ma,rec());
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> A[i][j];
			A[i][j]--;
		}
	}
	for (int i = 0; i < M; i++)st.insert(i);
	puts(rec());

	return 0;
}

Measured memory_bytes: 1024
#if defined(LOCAL)
#define PROBLEM_NAME "d"
const double _max_double_error = 1e-9;
#include "testutils.h"
#define L(x...) (debug(x, #x))
#define C(x...) CHECK(x)
#else
#define L(x, ...) (x)
#define C(x, ...) ;
#include <bits/stdc++.h>
#endif

using namespace std;
using vi = vector<int>; using vvi = vector<vi>;
using ii = pair<int,int>; using vii = vector<ii>;
using l = long long; using vl = vector<l>; using vvl = vector<vl>;
using ll = pair<l,l>; using vll = vector<ll>; using vvll = vector<vll>;
using lu = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vd = vector<double>; using vvd = vector<vd>;
using mll = unordered_map<l, l>;
const l INF = numeric_limits<l>::max();
const double EPS = 1e-10; static constexpr auto PI = acos(-1);
const l e0=1, e3=1000, e5=100000, e6=10*e5, e7=10*e6, e8=10*e7, e9=10*e8;
const char lf = '\n';
#define all(x) begin(x), end(x)
#define F(a,b,c) for (l a = l(b); a < l(c); a++)
#define B(a,b,c) for (l a = l(c) - 1; a >= l(b); a--)
#define MAX(a,b)({__typeof__(a)__x=(a);__typeof__(b)__y=(b);__x<__y?__y:__x;})
#define MIN(a,b)({__typeof__(a)__x=(a);__typeof__(b)__y=(b);__x<__y?__x:__y;})

void solve(istream& cin, ostream& cout) {
  l n, k; cin >> n >> k;
  vll v(n); F(i, 0, n) cin >> v[i].first >> v[i].second;
  sort(all(v));
  l answer = INF;
  F(i, 0, n) {
    vl y;
    F(j, i, n) {
      y.emplace_back(v[j].second);
      sort(all(y));
      if (y.size() < k) continue;
      F(a, 0, y.size() - k + 1) {
        answer = min((v[j].first - v[i].first) * (y[a + k - 1] - y[a]), answer);
      }
    }
  }
  cout << answer << lf;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(15);
#if defined(LOCAL)
  // _generate_random_test = generate_random;
  // _solve_brute = solve_brute;
  // _player_b = player_b;
  // _custom_solution_checker = solution_checker;
  maybe_run_tests(cin, cout);
#else
  solve(cin, cout);
#endif
}


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

int main(){

  char ch[4];
  for(int i=0;i<4;i++) cin >> ch[i];

  int front, back;

  front = 10*(ch[0]-'0') + (ch[1]-'0');
  back = 10*(ch[2]-'0') + (ch[3]-'0');

  //cout << front << " " << back <<endl;

  if(1<=front && front<=12){
    if(1<=back && back<=12){
      cout << "AMBIGUOUS" <<endl;
    }else{
      cout << "MMYY" <<endl;
    }
  }else{
    if(1<=back && back<=12){
      cout << "YYMM" <<endl;
    }else{
      cout << "NA" <<endl;
    }
  }
  
  return 0;
}













Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 10000


int main(){
  int n,m,a,b;
  int d[SIZE];

  scanf("%d%d%d%d",&n,&m,&a,&b);
  for(int i=0;i<n;i++) scanf("%d",d+i);

  int t = 0;
  
  for(t=0;t<n;t++){
    if(d[t] < a) break;
  }
  
  if(n-t < m){

    for(;t>0;t--){
      if(d[t-1] > b) break;
    }

  }

  printf("%d\n",t);
  
  return 0;
}

Measured memory_bytes: 3220
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

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

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

#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);

int main() {
    fast_io;

    ll a,b,c,k;

    cin>>a>>b>>c>>k;

    ll ans=0;
    if(k<=a) {
        ans+=k;
        cout<<ans<<endl;
        return 0;
    }
    else {
        k-=a;
        ans+=a;
    }

    if(k<=b) {
        cout<<ans<<endl;
        return 0;
    }
    else {
        k-=b;
    }

    if(k<=c) {
        ans-=k;
        cout<<ans<<endl;
        return 0;
    }

}




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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll x;
    cin >> x;
    ll size = 300000;
    bool is_prime[size];
    memset(is_prime, true, sizeof is_prime);
    is_prime[0] = false;
    is_prime[1] = false;
    repd(i, 2, size) {
        if (is_prime[i]) {
            ll index = i * 2;
            while (index < size) {
                is_prime[index] = false;
                index += i;
            }
        }
    }
    repd(i, x, size) {
        if (is_prime[i]) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 512
n = int(input())
d = [int(x) for x in input().split()]
mod = 998244353
m = [0]*n

for x in d:
    m[x] += 1
ans = 1

if d[0] != 0 or m[0] > 1:
    print(0)
else:
    for i in range(1, n):
        ans *= pow(m[i-1], m[i], mod)
        ans %= mod
    print(ans)

Measured memory_bytes: 14396
#include <iostream>
#include<set>
#include<vector>
#include<string>
using namespace std;
int mod=1000000007;
int inv=(mod+1)/2;
int add(int x, int y)
{
	int c=x+y;
	if(c>=mod)c-=mod;
	return c;
}
int sub(int x, int y)
{
	int c=x-y;
	if(c<0)c+=mod;
	return c;
}
int mlt(int x, int y)
{
	long long c=x*1LL*y;
	if(c>=mod)c%=mod;
	return c;
}
vector<int>rec(vector<int>&dp, int m)
{
	vector<int>res(m+1), dpml(m+1), pref(m+1), pows(m+1), dvas(m+1);
	pows[0]=1;
	dvas[0]=1;
	for(int i=1; i<=m; i++)
	{
		pows[i] = mlt(pows[i - 1], inv);
		dvas[i] = mlt(dvas[i - 1], 2);
	}
	res[1]=add(dp[1],dp[1]);
	for(int i=1; i<=m-1; i++)
	{
		dpml[i]=mlt(dp[i], mlt(pows[i+1], i));
	}
	pref[0]=0;
	for(int i=1; i<m; i++)
		pref[i]=add(pref[i-1], dpml[i]);
	for(int i=2; i<=m; i++)
	{
		res[i]=mlt(dp[i], i+1);
	//	cout<<i<<' '<<res[i]<<endl;
		int val=pref[i-1];
		val=mlt(val, dvas[i]);
		res[i]=add(res[i], val);
	}
	return res;
}
int main()
{
	string s;
	cin>>s;
	for(int i=0; i<s.length(); i++)
	{
		if(s[i]=='P')cout<<'P';
		else cout<<'D';
	}
}


Measured memory_bytes: 3756
/* B */

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int n;
	cin >> n;
	std::vector<int> v(n);

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

	int cnt = 0;

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

	cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9
void swap(ll &a,ll &b){
	ll tmp = a;
	a = b;
	b = tmp;
	return;
}

int main(){

 ll a,b,k;
 cin>>a>>b>>k;
 for(int i=0;i<k;i++){
	a/=2;
	b+=a;
	//cout<<a<<' '<<b<<endl;
	swap(a,b);
	//cout<<a<<' '<<b<<endl;
 }
 	if(k%2==1)swap(a,b);
	cout<<a<<' '<<b<<endl;

	return 0;
}


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

int main()
{
	
	int n;
	cin>>n;
	int i;
	int s=0;
	for(i=1;i<=n;i++)
	{
		s=s+i;
		
	}
	
	cout<<s<<endl;
	

	return 0;
	
}

Measured memory_bytes: 3544
#include <stdio.h>
int main(){
  int a,b,city[4]={0,0,0,0},judge=0;
  for (int i=0;i<3;i++){
    scanf("%d%d",&a,&b);
    city[a-1]++;
    city[b-1]++;
  }
  for (int i=0;i<4;i++){
    if (city[i]==0 || city[i]>2){
      printf("NO\n");
      break;
    }
    judge++;
  }
  if (judge==4){
    printf("YES\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  vector<int> t(n);
  vector<int> a(n);
  REP(i,0,n) {
    cin >> t[i];
  }
  REP(i,0,n) {
    cin >> a[i];
  }
  vector<pair<int,int>> vt(n);
  vector<pair<int,int>> va(n);
  REP(i,0,n) {
    int pt = i == 0 ? 1 : t[i-1];
    vt[i].first = t[i];
    vt[i].second = pt == t[i] ? 1 : t[i];
  }
  for(int i=n-1; i>=0; i--) {
    int pa = i == n-1 ? 1 : a[i+1];
    va[i].first = a[i];
    va[i].second = pa == a[i] ? 1 : a[i];
  }
  ll c = 1;
  REP(i,0,n) {
    int u = min(vt[i].first, va[i].first);
    int l = max(vt[i].second, va[i].second);
    int x = u - l + 1;
    if(x < 1) {
      c = 0;
      break;
    }
    c = (c * (x % MOD)) % MOD;
  }
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 2560