akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

int main(){

  int n, k;
  cin >> n >> k;

  int a[200001];
  for (int i = 0; i <= n; i++){
    a[i] = 0;
  }
  for (int i = 0; i < n; i++){
    int k;
    scanf("%d", &k);
    a[k]++;
  }
  priority_queue<pair<int, int> > pq;
  for (int i = 0; i <= n; i++){
    if (a[i] != 0){
      pq.push(make_pair(-a[i], i));
    }
  }
  int t = pq.size();
  int ans = 0;
  for (int i = 0; i < t - k; i++){
    pair<int, int> u = pq.top(); pq.pop();
    ans += u.first;
  }
  cout << -ans << "\n";
  return 0;
}


Measured memory_bytes: 3188
#include <iostream>
#include<algorithm>
using namespace std;
int n[1919];

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

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

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

	int a = 0;
	int b = 0;
	int c = 0;
	int d = 0;
	for (int ii = 0; ii < N; ++ii){
		string s;
		cin >> s;
		if (s == "AC"){
			a++;
		}
		if (s == "WA"){
			b++;
		}
		if (s == "TLE"){
			c++;
		}
		if (s == "RE"){
			d++;
		}
	}

	printf("AC x %i\n", a);
	printf("WA x %i\n", b);
	printf("TLE x %i\n", c);
	printf("RE x %i\n", d);

	return 0;
}


Measured memory_bytes: 3716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll t1,t2,a1,a2,b1,b2;
	cin>>t1>>t2;
	cin>>a1>>a2;cin>>b1>>b2;	
	ll x=a1*t1+a2*t2,y=b1*t1+b2*t2;
	if(x==y)cout<<"infinity"<<endl;
	else if((x>y&&a1<b1)||(x<y&&a1>b1)){
		ll t=(a1-b1)*t1;
		ll d=y-x;
		if(t%d!=0)cout<<t/d*2+1<<endl;
		else cout<<t/d*2<<endl;
	}
	else cout<<0<<endl;
    return 0;
}

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

int main(){
    string S;
    cin >> S;
    ll N = S.size();

    ll i = 0;
    while(i != N){
        if(N - i < 5){
            cout << "NO" << endl;
            return 0;
        }
        if(S.substr(i, 5) == "dream"){
            i += 5;
            if(i < N-1 && S.substr(i, 2) == "er"){
                if(i <= N-3 && S[i+2] != 'a') i += 2;
                else if(i == N-2) i += 2;
            }
        }else if(S.substr(i, 5) == "erase"){
            i += 5;
            if(i < N && S[i] == 'r') i++;
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 512
import sys
readline = sys.stdin.readline

N = int(readline())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
A, B = map(list, zip(*AB))

ans = min(sum(A), sum(B))
C = [(A[i], i) for i in range(N)] + [(B[i], i) for i in range(N)]

C.sort()

table = [0]*N
for i in range(N):
    _, idx = C[i]
    table[idx] += 1
if max(table) > 1:
    ans = min(ans, sum(c for (c, _) in C[:N]))

else:
    MAB = list(map(max, AB))
    D = [None]*N
    for i in range(N, 2*N):
        _, idx = C[i]
        D[idx] = i
    
    res = sum(c for (c, _) in C[:N])
    for i in range(N-1):
        _, idx = C[i]
        ans = min(ans, res + MAB[idx] - C[N-1][0])
    ans = min(ans, res + MAB[C[N-1][1]] - C[N-2][0])

print(ans)

Measured memory_bytes: 74716
n,m = list(map(int,input().split()))

A = [[0 for q in range(m)] for w in range(n)]
B = [0 for e in range(m)]

for i in range(n):
	A[i] = list(map(int, input().split()))
for j in range(m):
	B[j] = int(input())

for i in range(n):
	c = 0
	for j in range(m):
		c += A[i][j] * B[j]
	print(c)

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int Q, H, S, D, N;
	cin >> Q >> H >> S >> D >> N;
	H = min(H, 2 * Q);
	S = min(S, 2 * H);
	D = min(D, 2 * S);

	long long res = 0;
	res += 1LL * D * (N / 2); N %= 2;
	res += 1LL * S * N;

	cout << res << endl;
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; cin >> N;
    vector<LDP> pv(N);
    rep(i, N){
        int x, y; cin >> x >> y;
        pv[i] = make_pair(x, y);
    }
    sort(all(pv));

    double res = 0;
    do{
        rep(i, N-1){
            auto x1 = pv[i].first, y1 = pv[i].second;
            auto x2 = pv[i+1].first, y2 = pv[i+1].second;
            double tmp = (x1 -x2) * (x1-x2) + (y1-y2) * (y1-y2);
            res += sqrt(tmp);
        }
    }while(next_permutation(all(pv)));

    cout << res / (double)fact[N] << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

int main()
{
    int X;
    cin >> X;
    int ure500 = X / 500;
    X -= ure500*500;

    int ure5 = X / 5;
    

    cout << ure500 * 1000 + ure5*5 << endl;
}

Measured memory_bytes: 256
// C - Go Home

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

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

	int k = 0;
	int ans;
	for (int i=1;;i++) {
		k += i;
		if (k >= X) {
			ans = i;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

struct node { int parent, left, right; };
node t[100005];

int main() {

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		t[i].parent = -1;
		t[i].left = -1;
		t[i].right = -1;
	}

	for (int i = 0; i< n; i++) {
		int k;
		int nodenum;
		int c;
		cin >> nodenum >> k;

		int d = 0;
		for (int j = 0; j < k; j++) {

			cin >> c;
			if (j == 0) {
				t[nodenum].left = c;
				d = c;
			}
			else {
				t[t[nodenum].left].right = c;
				t[nodenum].left = c;
			}
			t[c].parent = nodenum;
			if (j == k - 1) {
				t[nodenum].left = d;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << "node " << i << ": parent = " << t[i].parent << ", depth = ";
		int counter = 0;
		int tmp = i;
		while (t[tmp].parent != -1) {
			tmp = t[tmp].parent;
			counter++;
		}

		cout << counter << ", ";

		if (t[i].parent == -1) {
			cout << "root, [";
		}
		else if (t[i].left == -1) {
			cout << "leaf, [";
		}
		else {
			cout << "internal node, [";
		}

		tmp = t[i].left;
		counter = 0;
		while (tmp!=-1) {
			if (counter == 0) {
				cout << t[i].left;
			}
			else {
				if (t[tmp].right == -1) {
					break;
				}
				cout << ", " << t[tmp].right;
				tmp = t[tmp].right;
			}
			counter++;
		}
		cout << "]" << endl;


	}


}


Measured memory_bytes: 4252
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin >> N;
  vector<string>blue(N);
  vector<int>bc(N);
  for (int i=0; i<N; i++) cin >> blue.at(i);
  cin >> M;
  vector<string>red(M);
  for (int i=0; i<M; i++) cin >> red.at(i);
  for (int i=0; i<N; i++){
    for (int j=0; j<N; j++){
      if(blue.at(i) == blue.at(j)) bc.at(i)++;
    }
  }
  for (int i=0; i<N; i++){
    for (int j=0; j<M; j++){
      if(blue.at(i) == red.at(j)) bc.at(i)--;
    }
  }
  int ans=0;
  for (int i=0; i<N; i++){
    ans = max(bc.at(i), ans);
  }
  cout << ans << endl;
}

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

int a[3];

int main(){
  int K;
  cin >> a[0] >> a[1] >> a[2] >> K;
  sort(a,a+3);
  for (int i = 0; i < K; i++) {
    a[2]*=2;
  }
  cout << a[0] + a[1] + a[2] << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli mod=1000000007;
#define Jaldi_jaldi_kar_subha_panvel_ke_liye_nikalna_hai ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    Jaldi_jaldi_kar_subha_panvel_ke_liye_nikalna_hai
    lli n;
    cin>>n;
    lli arr[n];
    for(lli i=0;i<n;++i)
    	cin>>arr[i];
    lli ans=LLONG_MAX;
    for(lli p=1;p<=100;++p){
    	lli cost=0;
    	for(lli i=0;i<n;++i){
    		cost+=abs(arr[i]-p)*abs(arr[i]-p);
    	}
    	if(cost<ans)
    		ans=cost;
    	cost=0;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
N, D = gets.split.map(&:to_i)
XS = N.times.map { gets.split.map(&:to_i) }

ans = 0
XS.combination(2) do |xs1, xs2|
  sum = 0
  D.times do |i|
    sum += (xs1[i] - xs2[i])**2
  end

  sq = Math.sqrt(sum)
  ans += 1 if sq == sq.to_i
end

puts ans


Measured memory_bytes: 1788
<?php /*atcoder.php*/

$t = new temp();

$t->stdin(fgets(STDIN));

unset($t);

class temp{
	private $stdin = array();
	
	public function __construct(){
	}

	public function stdin($data = null){
		$this->stdin = explode(" ", $data);
		$f = false;

		$a = array(3433 , 3449 , 3457 , 3461 , 3463 , 3467 , 3469 , 3491 , 3499 , 3511 , 3517 , 3527 , 3529 , 3533 , 3539 , 3541 , 3547 , 3557 , 3559 , 3571);
	
		$buf = 0;

		foreach($a as $v){
			$buf = $this->stdin[0] * $v;
			if(0 != $buf % $this->stdin[1]){
				echo $buf;
				break;
			}
			if(3571 == $v){
				echo "-1";
			}
		}
		unset($v);
	}	
	
}

?>


Measured memory_bytes: 3956
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <locale>
using namespace std;
#define MS0(I) memset(I, 0, sizeof(I));
#define MS1(I) memset(I, -1, sizeof(I));
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, s, n) for(int i = (s); i < (n); ++i)
#define per1(i, a, b) for(int i = a; i >= b; --i)
#define DRI(A) int A; scanf("%d", &A);
#define DRII(A, B) int A, B; scanf("%d %d", &A, &B);
#define DRIII(A, B, C) int A, B, C; scanf("%d %d %d", &A, &B, &C);
#define SZ(X) ((int)X.size() )
#define MP make_pair 
#define pb push_back
#define F first
#define S second
#define ALL(I) (I).begin(), (I).end()
typedef const void CV;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef long double LDB;
typedef pair<int, int> PII; 
const double eps = 1e-9;
const double PI = acos(-1);
const LL INFF = 1e18;
const int INF = 1e9;
const int mod = 1e9+7;
const int MAX = 1e5+7;
int main(void){
	DRII(a, b);
	if(a+b == 15) puts("+");
	else if(a*b == 15) puts("*");
	else puts("x");
	return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

# print(H, W)
# print(N)
# print(A)

# 上下連結していないといけない
# 解が存在する
# 順番に置いていけばよい

build_order = []
for i in range(H):
    if i % 2 == 0:
        for j in range(W):
            build_order.append((i, j))
    else:
        for j in range(W - 1, -1, -1):
            build_order.append((i, j))

colors = [[None for _ in range(W)] for _ in range(H)]

index = 0
color = 0

while index < W * H:
    c = A[color]
    k = 0
    while k < c:
        (i, j) = build_order[index]
        index += 1
        k += 1
        colors[i][j] = color + 1
    color += 1

for c in colors: print(" ".join(map(str, c)))

Measured memory_bytes: 40944
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
const ll INF=1e15;

inline bool ok(ll i,ll b,ll s,ll n){
  ++b;
  //if(i==1) cout<<pii(s-i<b , b*b>n )<< s-i<<endl;
  return i<b && s-i<b && !(b<=n/b) && s-i>=0;
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  ll n,s;
  cin>>n>>s;
  for(ll b=2;b*b<=n;++b){
    ll tmp=0;
    for(ll i=n;i;i/=b) tmp+=i%b;
    if(tmp==s){
      cout<<b<<endl;
      return 0;
    }
  }
  ll re=INF;
  for(ll i=1;i*i<=n-s;++i) if((n-s)%i==0){
      if(ok(i,(n-s)/i,s,n)) MN(re,(n-s)/i+1);
      if(ok((n-s)/i,i,s,n)) MN(re,i+1);
    }
  if(n==s) MN(re,n+1);
  cout<<(re==INF?-1:re)<<endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  set<int> S;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    S.insert(a);
  }
  int n=S.size();
  cout << n << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))

B = [0] * N
for i in range(N-1,-1,-1):
    n = 1
    SUM = 0
    while (i+1) * n < N+1:
        m = (i+1) * n -1
        SUM += B[m]
        n += 1
    if SUM % 2 == A[i]:
        B[i] = 0
    else:
        B[i] = 1

ans = []
for i,b in enumerate(B):
    if b == 1:
        ans.append(i+1)
print(len(ans))
print(*ans)


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

#define cn count
#define pb push_back
#define in insert
#define fs first
#define sc second
#define sz size
#define len length
#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define forni(i, n) for (ll i = 1; i < (ll) (n); ++i)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;
using ll = long long;
const ll inf = 1e9+7; 
const double PI =  3.141592653589793;

int main(){
	IO;
	ll n,a,cnt=0;
	cin>>n;
	forn(i,n){
		cin>>a;
		if(a!=i+1)cnt++;
	}
	(cnt==2 || cnt==0)?cout<<"YES\n":cout<<"NO\n";
	return 0;
}

// _   .-')                .-. .-')                 .-')                                               
//( '.( OO )_              \  ( OO )               ( OO ).                                             
// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 
// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '
// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |
// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |
// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |
// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '
// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""


Measured memory_bytes: 3636
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

constexpr int gcd(int a, int b) {
  int c = 0;
  while (a) {
    c = a;
    a = b % a;
    b = c;
  }
  return b;
}

void solve() {
  int a, b;
  while (cin >> a >> b) cout << gcd(a, b) << endl;
}

Measured memory_bytes: 3016
K, A, B = map(int, input().split())

if A >= B:
    ans = K+1
else:
    if A-1 >= K:
        ans = K+1
    else:
        ans = A
        K2 = K - (A-1)
        ans += (B-A) * (K2//2)
        ans += K2%2
        ans = max(ans, K+1)
print(ans)


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

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define INF_LL 2000000000000000000LL
#define INF 1000000000
#define EPS 1e-8
#define LL long long
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define setzero(a) memset(a,0,sizeof(a))
#define setdp(a) memset(a,-1,sizeof(a))
#define bits(a) __builtin_popcount(a)

using namespace std;

vector<int> nxt[100005];

int solve(int ind) {
	int ans = 0;
	vector<int> v;
	for (int x : nxt[ind]) {
		v.pb(solve(x));
	}
	sort(v.begin(), v.end(), greater<int>());
	for (int i=0;i<v.size();i++) {
		ans = max(ans, v[i] + i + 1);
	}
	return ans;
}

int main() {
	int n, x;
	cin >> n;
	for (int i=1;i<n;i++) {
		scanf("%d", &x);
		nxt[x-1].pb(i);
	}
	cout << solve(0);
	return 0;
}

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    int arr[3];
    arr[0] = 0; arr[1] = 0; arr[2] = 0;
    int x,y,z,a,b,c;
    for (int aa = 0; aa < N; aa++) {
        cin >> x >> y >> z;
        a = max(arr[1],arr[2])+x;
        b = max(arr[0],arr[2])+y;
        c = max(arr[0],arr[1])+z;
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
    }
    if (a > b) {
        cout << max(a,c);
    }
    else {
        cout << max(b,c);
    }
}

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

int main(){
 string s;
  cin>> s;
  if(s=="Sunny"){
  cout << "Cloudy" << endl;
  }if(s=="Cloudy"){
  cout << "Rainy" << endl;
  }if(s=="Rainy"){
  cout << "Sunny" << endl;
  }
}

Measured memory_bytes: 256
n, k = map(int, input().split()) 
L = list(i for i in range(1,n+1))
for i in range(k):
  d = int(input())
  A = list(map(int, input().split()))
  for j in A:
    L = [0 if m == j else m for m in L]
  
print(n-L.count(0))


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

#include <unistd.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
 
 
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx_ori[4] = { -1,0, 1,0 }, dy_ori[4] = { 0,1,0,-1 };
int dx[4] = {0, 0, 0, 0}, dy[4] = {0, 0, 0, 0};
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
// #define mp make_pair
//#define endl '\n'

signed main() {
  int n, t;
  cin >> n >> t;
  vi a(n);
  rep (i, n) cin >> a[i];

  int mi = inf;
  int sub = 0;
  int ans = 0;
  rep (i, n) {
    if (a[i] - mi > sub) {
      ans = 1;
      chmax(sub, a[i] - mi);
    }
    else if (a[i] - mi == sub) {
      ans++;
    }
    chmin(mi, a[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple {
    string s;
    void Solve() {
        //input
        s = io.String;
        //cal
        string ans = string.Join(" ", s.Split(','));
        //res
        Console.WriteLine(ans);
    }

    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() {
        Solve();
        io.writeFlush();
    }
}

class SimpleIO {
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define MAX(a,b) a=a>b?a:b
#define MIN(a,b) a=a<b?a:b
#define REP(i,x,n) for(int i=x;i<n;i++)
#define REPR(i,x,n) for(int i=n-1;i>=x;i--)
#define pb  push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLr(obj) (obj).rbegin(), (obj).rend()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
int main(){
   ll a,b,n;
   cin>>a>>b;
   if(a==1||b==1)cout<<1;
   else if(a%2==0||b%2==0)cout<<a*b/2;
   else 
   cout<<a*b/2+1;
   cout<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>

int solve(int,int);

int a[2000],n;

main(){
  int i,j,q,p;
  int m[2000];
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  } 
  
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m[i]);
  }
  
  for(i=0;i<q;i++){
    if(solve(0,m[i])==1)printf("yes\n");
    else printf("no\n");
    
  }
  return 0;
}

int solve(int i,int m){
  if(m == 0)return 1;
  if(i >= n)return 0;
  int res = solve(i + 1, m) || solve(i + 1, m - a[i]);
  return res;
}

Measured memory_bytes: 588
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define se set<ll>
#define vec vector<ll>
#define inf 10000000000000000
bool mark[100005];
vec adj[100005];
ll counter;
vec cnt;
vector<string> forsubs;
ll b;
ll a;
ll ans=1000000000000;
ll n;


int main()
{    
 

	#ifdef APNA_IO
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
		    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 


ll x,a;
cin>>x>>a;

if(x<a)
	cout<<"0"<<endl;
else
	cout<<"10"<<endl;

}



















		





Measured memory_bytes: 2560
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int main(void) {
	char S[7];

	scanf("%s",S);
	if(S[2]!=S[3]) {printf("No");return 0;}
	if(S[4]!=S[5]) {printf("No");return 0;}
	printf("Yes");


	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define END '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define trace(x) cerr<<x<<END;
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, b, a) for(int i = (b); i > (a); --i) 
const int mod = 1e9+7;
const int mod1 = 998244353;
const int inf = 9223372036854775807ll;

void solve()
  {
   int n;
   cin>>n;
   string ans;
   while(n>0){
    char c = 'a' + (n-1)%26;
    cerr<<c<<" "<<n%26<<END;
    n = (n-1)/26;
    ans += c;
   }
   reverse(ans.begin(), ans.end());
   cout<<ans;
  } 
signed main()
 {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0); 
     solve();
  //cerr<<END<<1.0*clock();
  return 0;
} 

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define Mod 998244353
#define MOD 1000000007
using namespace std;
using lint = long long;
using vi = vector<lint>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

// cout << fixed << setprecision(12)

int main(){
  
  lint D; cin >> D;
  vi c(26); // contest 0-25
  for(lint i=0; i<26; i++) cin >> c[i];
  vvi s(D+1, vi(26)); // day 0-D
  for(lint d=1; d<=D; d++){
    for(lint j=0; j<26; j++){
      cin >> s[d][j];
    }
  }
  /*
  vi t(D+1); // day 0-D
  
  for(lint d=1; d<=D; d++){
    cin >> t[d];
    t[d]--;
  }
  */
  
  vi last(26,0);
  
  // lint ans = 0;
  vi ans(D+1);
  
  for(lint d=1; d<=D; d++){
    vi diff(26);
    
    for(lint i=0; i<26; i++){ // if contest i (0-25)
      // ans += s[d][t[d]];
      lint plus = s[d][i];
    
      // last[t[d]] = d;
      lint oldlast = last[i];
      last[i] = d;
    
      lint minus = 0;
    
      for(lint j=0; j<26; j++){
        // ans -= c[j] * (d - last[j]);
        minus += c[j] * (d - last[j]);
      }
      
      last[i] = oldlast;
      diff[i] = plus - minus;
    }
    
    vi oldiff = diff;
    sort(ALL(diff));
    lint t = -1;
    for(lint j=0; j<26; j++){
      if(oldiff[j] == diff[25]) t = j;
    }
    // cout << t+1 << endl;
    ans[d] = t+1;
    last[t] = d;
    
  }
  /*
  sort(ALL(c));
  lint tmp = 18; // delete suru kosuu
  for(lint j=0; j<tmp; j++) c.pop_back();
          
  for(lint d=1; d<=D; d++){
    cout << c[d%(26-tmp)] << endl;
  }
  */
  
  for(lint i=0; i<26; i++) last[i] = 0;
  
  lint score = 0;
  
  for(lint d=1; d<=D; d++){
    score += s[d][ans[d]];
    last[ans[d]] = d;
    for(lint j=0; j<26; j++){
      score -= c[j] * (d - last[j]);
    }
  }
  
  lint cnt = 0;
  while(cnt<10){
    lint rd = rand()%25;
    swap(ans[rd], ans[rd+1]);
    ////////
    lint score2 = 0;
    for(lint d=1; d<=D; d++){
      score2 += s[d][ans[d]];
      last[ans[d]] = d;
      for(lint j=0; j<26; j++){
        score2 -= c[j] * (d - last[j]);
      }
    }
    ////////
    if(score2 <= score){
      swap(ans[rd], ans[rd+1]);
      continue;
    }else{
      score = score2;
      cnt++;
    }
  }

  
  for(lint d=1; d<=D; d++) cout << ans[d] << endl;
}
      
      
    
  
  
  
  


Measured memory_bytes: 3704
#include <stdio.h>
#include <string.h>

#define BUF_SIZE 10

int main(void) {
    char str[BUF_SIZE + 2];
    scanf("%s", str);

    int flag = 0, ptr;
    for (ptr = 0; ptr < strlen(str); ptr += 2) {
        if (!strncmp("hi", (str + ptr), 2)) {
            flag = 1;
            continue;
        } else {
            flag = 0;
        }
    }

    if (flag) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
ll n,a;
bitset<4000005>b;
int main() {
slld(n);
ll s=0;
b.set(0);
for(int i=1;i<=n;i++)
{
	slld(a);
	s+=a;
	b|=(b<<a);
}
s++;
s/=2;
for(;!b[s];s++);
plld(s);
	return 0;
           } 

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> V(N);
  for (int i=0; i<N; i++){
  cin >> V.at(i);
  }
  
  int k=0;
  
  for (int i=0; i<N+1; i++){
    k = V.at(k) -1;
    if (k==1){
      cout << i+1 << endl;
      break;
    }
    else if( i==N ){
      cout << -1 << endl;
      break;
    }
  }
}

Measured memory_bytes: 3788
n, m = map(int, input().split())
K = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))

ans = 0

for i in range(2 ** n):
    switch = [0 for i in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            switch[n - 1 - j] = 1
    for l in range(m):
        cnt = 0
        for s in K[l][1:]:
            cnt += switch[s-1]
        if cnt % 2 != P[l]:
            break
    else:
        ans += 1

print(ans)


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

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

    string sun = "Sunny";
    string clo = "Cloudy";
    string rai = "Rainy";
    string w[3] = {sun, clo, rai};
    int i = 0;
    if (s == clo) i = 1;
    else if (s == rai) i = 2;

    cout << w[(i + 1) % 3];

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int H,W; cin>>H>>W;
	vector<string> S(H);
	for (int i=0; i<H; i++)
		cin>>S[i];
	int ret=0;
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) {
			if(S[i][j]=='#')
				continue;
			map<ii,int> dist;
			ii init={i,j};
			dist[init]=0;
			queue<ii> q; q.push(init);
			while(!q.empty()) {
				ii cur=q.front(); q.pop();
				ret=max(ret,dist[cur]);
				for (int k=0; k<4; k++) {
					ii nxt=cur; nxt.first+=dx[k]; nxt.second+=dy[k];
					if(nxt.first<0||nxt.first>=H||nxt.second<0||nxt.second>=W)
						continue;
					if(dist.count(nxt))
						continue;
					if(S[nxt.first][nxt.second]=='#')
						continue;
					dist[nxt]=dist[cur]+1;
					q.push(nxt);
				}
			}
		}
	}
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	
	long long int x;
	scanf("%lld", &x);
	
	long long int count = x / 11 * 2;
	x %= 11;
	
	if(x == 0) ;
	else if(x <= 6) count++;
	else count += 2;
	
	printf("%lld\n", count);
	return 0;
}

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

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

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int N = in.nextInt();
            int array[][] = CPUtils.readIntMatrix(N, 3, in);
            int best[] = new int[3];
            for (int i = 0; i < N; ++i)
            {
                int[] dp = new int[3];
                for (int j = 0; j < 3; ++j) // previous
                    for (int k = 0; k < 3; ++k)
                    { // next
                        if (j == k) continue;
                        dp[k] = Math.max(dp[k], best[j] + array[i][k]);
                    }
                best = dp;
            }
            out.print(CPUtils.maxArray(best));
        }

    }

    static class CPUtils
    {
        public static int[] readIntArray(int size, Scanner in)
        {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
            {
                array[i] = in.nextInt();
            }
            return array;
        }

        public static int[][] readIntMatrix(int rows, int columns, Scanner in)
        {
            int[][] matrix = new int[rows][columns];
            for (int i = 0; i < rows; i++)
            {
                matrix[i] = CPUtils.readIntArray(columns, in);
            }
            return matrix;
        }

        public static int maxArray(int[] array)
        {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < array.length; i++)
            {
                max = Math.max(max, array[i]);
            }
            return max;
        }

    }
}



Measured memory_bytes: 100788
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    ans = 20
    for i in range(-R + geta, R + geta):
        if i < geta:
            buildings[i] -= pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5) - R
        else:
            buildings[i] -= pow(R * R - (i - geta) * (i - geta), 0.5) - R
        ans = min(ans, buildings[i])
    print(ans)

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

int main(){
    int N,M; cin >> N >> M;
    int X,Y; cin >> X >> Y;
    int max = -10000,min = 10000;
    for(int i=0;i<N;i++){
        int x; cin >> x;
        if(max < x){
            max = x;
        }
    }
    for(int i=0;i<M;i++){
        int y; cin >> y;
        if(min > y){
            min = y;
        }
    }
    bool flag = true;
    for(int z=X+1;z<=Y;z++){
        if(max < z && z <= min ){
            cout << "No War" << endl;
            flag = false;
            break;
        }
    }
    if(flag){
        cout << "War" << endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }
  sort(a.begin(), a.end());
  
  int max1 = a[n-1], max2 = a[n-2];
  
  for (int i = 0; i < n; i++) {
    if (b[i] == max1) {
      cout << max2 << endl;
    }
    else {
      cout << max1 << endl;
    }
  }
}

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

long long n, m;

int main() {
    long long a = 100;
    cin >> n;
    if(n >= 1335850880) {
        a = 1335850880;
        int i = 0;
        while(a < n) {
            a = a + a * 0.01;
            i++;
        }
        cout << i + 1706;
        return 0;
    }
    int i = 0;
    while(a < n) {
        a = a + a * 0.01;
        i++;
    }
    cout << i;
    return 0;
}


Measured memory_bytes: 3652
N,X,Y = map(int,input().rstrip().split())
ans = [0 for _ in range(N)]
dis = [0,0]
xycent = (X + Y) / 2
for i in range(1 , N):
  for i2 in range(i + 1,N + 1):
    dis[0] = i2 - i
    dis[1] = abs(i - X) + abs(i2 - Y) + 1
    if dis[0] > dis[1]:
      ans[dis[1]] += 1
    else:
      ans[dis[0]] += 1
for i in range(1,N):
  print(ans[i])

Measured memory_bytes: 3444
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {
	
	final long MOD = (long)(1e9+7);
	
	void solve() {
		int N = sc.nextInt();
		int M = sc.nextInt();
		long[] xs = new long[N];
		long[] ys = new long[M];
		for (int i = 0; i < N; i++) xs[i] = sc.nextInt();
		for (int i = 0; i < M; i++) ys[i] = sc.nextInt();
		
		long uy = 0;
		for (int j = 1; j < M; j++) {
			uy += (long)j * (M - j) % MOD * (ys[j] - ys[j-1]) % MOD;
			uy %= MOD;
		}
		long ans = 0;
		for (int i = 1; i < N; i++) {
			ans += uy * (xs[i] - xs[i-1]) % MOD * i % MOD * (N - i) % MOD;
			ans %= MOD;
		}
		out.println(ans % MOD);
	}
	
	static void tr(Object... os) { System.err.println(deepToString(os)); }
	static void tr(int[][] as) { for (int[] a : as) tr(a); }

	void print(int[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

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

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}

Measured memory_bytes: 46032
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=1e6+19;
const int p=1e9+7;

int f[N],g[N];
int n;

int main(){
	n=IN();
	f[1]=g[1]=n;
	For(i,2,n+1){
		f[i]=(f[i-1]+1ll*(n-1)*(n-1))%p;
		if (i-3>0) f[i]=(f[i]+g[i-3])%p;
		f[i]=(0ll+f[i]+min(i-3,0)-(i-n-1)+1)%p;
		g[i]=(g[i-1]+f[i])%p;
	}
	printf("%d\n",f[n]);
}

Measured memory_bytes: 8064
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int P = 1e9 + 7;
inline void pp(int &x,int d) {
  if((x+=d)>=P) x-=P;
}

int main(){
  ll n , K;
  cin >> n >> K;
  vector<ll> a(n);
  rep(i,0,n) cin >> a[i];
  sort(all(a));
  map<vector<ll>,vector<pair<ll,ll> > > Mp;
  rep(d,0,61) {
    vector<ll> r;
    r.pb(0);r.pb(1ll<<d);
    rep(i,0,n) r.pb(a[i]%(1ll<<d)+1);
    sort(all(r));
    r.erase(unique(all(r)),r.end());
    rep(i,0,sz(r)-1) {
      ll from = r[i] , to = min(a[0] , r[i + 1] - 1);
      if(from > a[0])
        break;
      ll cost = d;
      per(d,0,61) {
        if((from >> d & 1) == (to >> d & 1))
          cost += from >> d & 1;
        else {
          if(from & ((1ll<<d)-1))
            cost++;
          break;
        }
      }
      ll remain = K - cost;
      if(remain >= 0) {
        vector<ll> na = a;
        for(auto&e:na) e = (e - from) >> d;
        vector<ll> dif(n - 1);
        ll del = min(na[0] , remain);
        rep(i,0,n-1) dif[i] = na[i + 1] - na[i];
        Mp[dif].pb(mp(na[0] - del , na[0]));
      }
    }
  }
  int ans = 0;
  for(auto e : Mp) {
    auto&v = e.se;
    sort(all(v));
    pair<ll,ll> last = v[0];
    rep(i,0,sz(v)) {
      if(v[i].fi <= last.se)
        last.se = max(last.se , v[i].se);
      else pp(ans , (last.se - last.fi + 1) % P) , last = v[i];
    }
    pp(ans , (last.se - last.fi + 1) % P);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 16384
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
const double  pi = 3.1415926535897932384626;
using namespace std;
int main() {
    cout << fixed << setprecision(20);
    int a, b;
    double h, m;
    cin >> a >> b >> h >> m;
    h = ((int)h%12) * 30 + 0.5 * m;
    m = m*6;
    double O = pi * (double) (fabs(h - m)) / 180.0;
   cout << sqrt(a*a + b*b - 2*a*b*cos(O));
   // system("pause");
}

/*
 * ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */


/*
3 4 10 40
4.56425719433005567605

*/

Measured memory_bytes: 4156
number = int(input())
outputlist = list()
count = 0
if number >= 1 and number <= 1000000:
    number = number + 1
    for i in range (1, number):
        if i % 3 == 0 and i % 5 == 0:
            outputlist.append("FizzBuzz")
        elif i % 3 == 0:
            outputlist.append("Fizz")
        elif i % 5 == 0:
            outputlist.append("Buzz")
        else:
            outputlist.append(str(i))
    for i in outputlist:
        if i.isdigit() == True:
            count = count + int(i)
        else:
            count = count
    print(count)
else:
    print()


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

int main() {
	int n,x;
	cin>>n>>x;
	int X[n];
	for(int i=0;i<n;i++){
		cin>>X[i];
		X[i]=abs(X[i]-x);
	}
	sort(&X[0],&X[n]);
	for(int i=X[0];i>0;i--){
		for(int j=0;j<n;j++){
			if(X[j]%i!=0){
				break;
			}else if(j==n-1){
				cout<<i<<endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 640
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
disc = []
for i in range(M):
  disc.append(list(map(int,input().split())))
ans = min(a) + min(b)
for i in range(M):
  ans = min(a[disc[i][0]-1] + b[disc[i][1]-1] - disc[i][2], ans)     
    
print(ans)

Measured memory_bytes: 80620
#include <cstdio>

using namespace std;

const int maxn=1e5+1e2;

int a[maxn];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		a[t1]++;
		a[t2]++;
	}
	bool flag=true;
	for(int i=1;i<=n;i++)if(a[i]&1)flag=false;
	if(flag)printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 640
N, A, B = map(int, input().split())
while(True):
    if A + 1 != B:
        A += 1
    elif A - 1 != 0:
        A -= 1
    else:
        print("Borys")
        break

    if B - 1 != A:
        B -= 1
    elif B + 1 != N + 1:
        B += 1
    else:
        print("Alice")
        break


Measured memory_bytes: 2940