#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include "message.h"
#include "krazki.h"

using namespace std;

long long a[2000010], c[2000010], mx[110], mn[110], moje1[2000010];
int b[2000010], d[2000010], e[2000010], f[110], pampara[110], moje2[2000010];

int main(){
	int x, n, k, m, y, v, t, ksz, psz, pocz, koni, woln;
	long long q, u, msz, nsz;
	x = PipeHeight();
	n = NumberOfNodes();
	k = NumberOfDiscs();
	m = MyNodeId();
	y = x / n;
	if (x % n > m)
		y++;
	t = (x / n) * m + min(x % n, m);
	if (y != 0)
		u = HoleDiameter(1 + t);
	v = 1 + t;
	for (int i = 2; i <= y; i++){
		q = HoleDiameter(i + t);
		if (q < u){
			b[0]++;
			a[b[0]] = u;
			b[b[0]] = v;
			u = q;
			v = i + t;
		}
	}
	b[0]++;
	a[b[0]] = u;
	b[b[0]] = v;
	q = a[b[0]];
	if (m > 0){
		Receive(m - 1);
		u = GetLL(m - 1);
		q = min(u, q);
	}
	if (m + 1 < n){
		PutLL(m + 1, q);
		Send(m + 1);
	}
	if (m > 0){
		v = t + 1;
		for (int i = 1; i <= b[0]; i++){
			if (q < a[i]){
				a[i] = q;
				b[i] = t + 1;
			}
		}
	}
	mx[m] = a[b[0]];
	mn[m] = a[1];
	for (int i = 0; i < n; i++){
		if (i == m)
			continue;
		PutLL(i, a[1]);
		PutLL(i, a[b[0]]);
		Send(i);
	}
	for (int i = 0; i < n; i++){
		if (i == m)
			continue;
		Receive(i);
		mn[i] = GetLL(i);
		mx[i] = GetLL(i);
	}
	y = k / n;
	if (k % n > m)
		y++;
	t = (k / n) * m + min(k % n, m);
	if (y != 0)
		c[1] = DiscDiameter(t + 1);
	d[0] = 1; d[1] = 1;
	for (int i = 2; i <= y; i++){
		q = DiscDiameter(i + t);
		if (q > c[d[0]]){
			d[0]++;
			c[d[0]] = q;
			d[d[0]] = 1;
		}
		else{
			d[d[0]]++;
		}
	}




	q = c[d[0]];
	if (m > 0){
		Receive(m - 1);
		u = GetLL(m - 1);
		q = max(u, q);
	}
	if (m + 1 < n){
		PutLL(m + 1, q);
		Send(m + 1);
	}
	if (m > 0){
		for (int i = 1; i <= d[0]; i++){
			if (q > c[i]){
				c[i] = q;
			}
		}
	}



	for (int i = 1; i <= d[0]; i++){
		int l, r;
		l = 1; r = n;
		int bin;
		while (mn[l - 1] != mn[r - 1]){
			bin = (r + l) / 2;
			if (mx[bin] < c[i])
				r = t;
			else{
				l = t;
			}
		}
		e[i] = r - 1;
		f[r - 1]++;
	}
	for (int i = 0; i < n; i++){
		if (i == m)
			continue;
		PutInt(i, f[i]);
		Send(i);
	}
	for (int i = 1; i <= d[0]; i++){
		if (e[i] == m){
			moje2[0]++;
			moje1[moje2[0]] = c[i];
			moje2[moje2[0]] = d[i];
		}
		else{
			PutLL(e[i], c[i]);
			PutInt(e[i], d[i]);
			pampara[e[i]] = pampara[e[i]] + 2;
			if (pampara[e[i]] = 8100){
				Send(e[i]);
			}
		}
	}
	for (int i = 0; i < n; i++){
		if (i == m)
			continue;
		if (pampara[i] != 0){
			Send(i);
		}
	}
	pocz = -1;
	int iter;
	for (int i = 0; i < n; i++){
		if (i == m){
			for (int j = 1; j <= moje2[0]; j++){
				int l, r, bin;
				l = 1; r = b[0];
				while (a[l] != a[r]){
					bin = (l + r) / 2;
					if (a[l] > moje1[i])
						l = bin;
					else
						r = bin;
				}
				if (pocz = -1){
					pocz = b[r];
					koni = b[r] - moje2[i] + 1;
				}
				else{
					koni = min(koni, b[r]) - ksz + 1;
					woln = woln + max(b[r] - koni, 0);
				}
			}
		}
		else{
			pampara[i] = 0;
			Receive(i);
			iter = GetInt(i);
			Receive(i);
			for (int j = 1; j <= iter; j++){
				msz = GetLL(i);
				ksz = GetInt(i);
				int l, r, bin;
				l = 1; r = b[0];
				while (a[l] != a[r]){
					bin = (l + r) / 2;
					if (a[l] > msz)
						l = bin;
					else
						r = bin;
				}
				if (pocz = -1){
					pocz = b[r];
					koni = b[r] - ksz + 1;
				}
				else{
					koni = min(koni, b[r]) - ksz + 1;
					woln = woln + max(b[r] - koni, 0);
				}
				pampara[i] = pampara[i] + 2;
				if (pampara[i] == 8100){
					pampara[i] = 0;
					Receive(i);
				}
			}
		}
	}
	if (m > 0){
		PutInt(0, pocz);
		PutInt(0, koni);
		PutInt(0, woln);
		Send(0);
	}
	else{
		int costam1, costam2, costam3, temp;
		for (int i = 1; i < n; i++){
			Receive(i);
			costam1 = GetInt(i);
			costam2 = GetInt(i);
			costam3 = GetInt(i);
			temp = costam2;
			temp = temp - max(costam3 - (costam1 - koni + 1), 0);
			koni = temp;
		}
	}
	cout << max(koni, 0);
	//system("pause");
}