#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
ll n , m;
ll x[100005] , y[100005];
vector<ll> a;
vector< pair<ll,ll> > v;
stack< pair<ll,ll> > S;
bool check(ll T)
{
        ll i = 0;
        ll curheight = 0;
        ll usedMissiles = 0;
        while(i < n) {

                ll j = i;
                ll maxHeight = v[i].second;
                while(j < n && v[j].first + T >= v[i].first) {
                        maxHeight = max(maxHeight , v[j].second);
                        j++;
                }
                usedMissiles++;
                curheight = max(curheight , maxHeight + T);
                while(j < n && v[j].second <= curheight) j++;
                i = j;
        }
        return (usedMissiles <= m);
}
class TheEmpireStrikesBack {
public:
	int find(int ax, int bx, int cx, int ay, int by, int cy, int N, int M) {
                ll AX = ax;
                ll BX = bx;
                ll CX = cx;
                ll AY = ay;
                ll BY = by;
                ll CY = cy;
                x[1] = AX;
                n = N;
                m = M;
                for(ll i=2;i<=n;i++) {

                        x[i] = ((x[i-1]*(1LL * BX))%MOD + (ll)CX)%MOD;
                }
                y[1] = AY;
                for(ll i=2;i<=n;i++) {

                        y[i] = ((y[i-1]*(1LL * BY))%MOD + (ll)CY)%MOD;
                }
                for(ll i=1;i<=n;i++) {
                        v.pb(make_pair(x[i] , y[i]));
                        //cout << x[i] << " " << y[i] << endl;
                }
                sort(v.rbegin() , v.rend());
                ll lo = 0;
                ll hi = MOD;
                while(hi > lo) {

                        ll mid = lo + (hi - lo) / 2;
                        if(check(mid)) {
                                hi = mid;
                        }else {
                                lo = mid+1;
                        }
                }
                return lo;
	}
};


<%:testing-code%>
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!