#include "message.h"
#include "krazki.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
//#define DEBUG

typedef vector<pair<long long, int>>::reverse_iterator vtype;

const int MAX_N = 102;
const long long LL = 1ll << 62;

int N, pid, n, m;

vector<pair<long long, int> > P, D;

struct strcmp {
	bool operator()(const pair<long long, int> &a, long long b) {
		return a.first < b;
	}
};

struct Meta {
	// Preprocessing
	int pipe_beg, pipe_end;
	int disc_beg, disc_end;

	// Gain from messages
	long long up_pipe, down_pipe;
	long long up_disc, down_disc;
};

Meta blocks[MAX_N];
pair<int, int> A[MAX_N];

void root() {
	int act = n + 1;
	for(int i = 1; i <= N; i++) {
		Receive(i);
		A[i].first = GetInt(i);
		A[i].second = GetInt(i);
		#ifdef DEBUG
		printf("A %d %d\n", A[i].first, A[i].second);
		#endif
		act = min(A[i].first, act - A[i].second);
		act = max(0, act);
	}

	printf("%d\n", act);
}

void explore_pipes() {
	if(blocks[pid].pipe_beg > n) {
		blocks[pid].up_pipe = LL;
		blocks[pid].down_pipe = LL;
		return;
	}
	P.push_back(make_pair(
		HoleDiameter(blocks[pid].pipe_beg), 1)
	);
	for(int i = blocks[pid].pipe_beg + 1; i <= blocks[pid].pipe_end; i++) {
		long long t = HoleDiameter(i);
		if(t >= P.back().first) P.back().second++;
		else P.push_back(make_pair(t, P.back().second + 1));
	}

	blocks[pid].up_pipe = P.front().first;
	blocks[pid].down_pipe = P.back().first;
}

void explore_discs() {
	if(blocks[pid].disc_beg > m) {
		blocks[pid].up_disc = 0;
		blocks[pid].down_disc = 0;
		return;
	}
	D.push_back(make_pair(
		DiscDiameter(blocks[pid].disc_beg), 1)
	);
	for(int i = blocks[pid].disc_beg + 1; i <= blocks[pid].disc_end; i++) {
		long long t = DiscDiameter(i);
		if(t <= D.back().first) D.back().second++;
		else D.push_back(make_pair(t, D.back().second + 1));
	}

	blocks[pid].up_disc = D.back().first;
	blocks[pid].down_disc = D.front().first;
	if(D.size() > 1) {
		D.back().second = D.back().second - D[D.size() - 2].second;
		for(int i = D.size() - 3; i >= 0; i--) {
			D[i + 1].second = D[i + 1].second - D[i].second + D[i + 2].second;
		}
		D[0].second = D[0].second + D[1].second;
	}

	reverse(D.begin(), D.end());

	#ifdef DEBUG
		if(pid >= 1) {
			printf("Disc Preprocessing\n");
			for(vector<pair<long long, int> >::iterator x = D.begin(); x != D.end(); x++) printf("%lld %d\n", x->first, x->second);
		}
	#endif
}

void normalize_pipes() {
	long long mini = blocks[1].down_pipe;
	for(int i = 2; i <= N; i++) {
		blocks[i].up_pipe = min(mini, blocks[i].up_pipe);
		blocks[i].down_pipe = min(mini, blocks[i].down_pipe);
		mini = min(mini, blocks[i].down_pipe);
	}

	#ifdef DEBUG
	if(pid == 1) {
		printf("Normalized pipes\n");
		for(int i = 1; i <= N; i++)
			printf("%lld %lld\n", blocks[i].up_pipe, blocks[i].down_pipe);
	}
	#endif
}

pair<int,int> find_my_blocking_step() {
	int first_blocking_block = N + 1;
	for(int i = 1; i <= N; i++) {
		if(blocks[pid].up_disc > blocks[i].up_pipe) {
			first_blocking_block = i;
			break;
		}
	}

	int first_good_hole = blocks[first_blocking_block].pipe_beg, end = 0;
	if(first_blocking_block == N + 1)
		first_good_hole = n;
	while(first_good_hole >= 1) 
		if(HoleDiameter(first_good_hole) >= D[0].first) {
			end = first_good_hole + 1;
			break;
		}
		else
			first_good_hole --;

	int up = end - D[0].second;
	#ifdef DEBUG
	for(vector<pair<long long, int>>::iterator it = D.begin(); it != D.end(); it++) printf("D %d %d\n", it->first, it->second);
	printf("END %d %d %d %d\n", pid, first_blocking_block, blocks[first_blocking_block].pipe_beg, end);
	printf("%d %d %d\n", up, D[0].second, end);
	#endif
	for(int i = end + 1, j = D.back().second; i <= n && j > 0; j--, i++) {
		long long t = HoleDiameter(i);
		vector<pair<long long, int>>::reverse_iterator ptr = upper_bound(D.rbegin(), D.rend(), make_pair(t, 1 << 30));
		if(ptr != D.rend()) up = min(up, i - ptr->second);
	}

	return make_pair(up, D.back().second);
}

void node() {
	explore_pipes();
	explore_discs();

	for(int i = 1; i <= N; i++) {
		if(i == pid) continue;
		PutLL(i, blocks[pid].up_pipe);
		PutLL(i, blocks[pid].down_pipe);
		Send(i);
	}

	for(int i = 1; i < N; i++) {
		int source = Receive(-1);
		blocks[source].up_pipe = GetLL(source);
		blocks[source].down_pipe = GetLL(source);
	}

	normalize_pipes();
	pair<int,int> f = find_my_blocking_step();

	PutInt(0, f.first);
	PutInt(0, f.second);
	Send(0);
}

void split_blocks() {
	int pipe_block = n / N;
	for(int i = 1, nr = 1; i <= N; i++, nr += pipe_block) {
		blocks[i].pipe_beg = nr;
		blocks[i].pipe_end = min(nr + pipe_block - 1, n);
	}
	blocks[N].pipe_end = n;

	int disc_block = m / N;
	for(int i = 1, nr = 1; i <= N; i++, nr += disc_block) {
		blocks[i].disc_beg = nr;
		blocks[i].disc_end = min(nr + disc_block - 1, m);
	}
	blocks[N].disc_end = m;

	#ifdef DEBUG
	if(pid == 1) {
		for(int i = 1; i <= N; i++) {
			printf("%d %d // %d %d\n", blocks[i].pipe_beg, blocks[i].pipe_end, blocks[i].disc_beg, blocks[i].disc_end);
		}
	}
	#endif
}

int main() {
	N = NumberOfNodes();
	N --;
	pid = MyNodeId();

	n = PipeHeight();
	m = NumberOfDiscs();
	N = min(N, max(1, n / 2));
	N = min(N, max(1, m / 2));
	//printf("%d %d\n", N, m);
	split_blocks();
	if(pid == 0) root();
	else if(pid <= N) node();
}