(Analysis by Benjamin Qi)

For each springboard $i,$ let $ans[i]$ denote the minimum distance needed to walk to the start point of springboard $i$. If Bessie walks directly to this springboard, then the distance is $x_1[i]+y_1[i].$ Otherwise, Bessie last took some springboard $j$ before walking to springboard $i,$ giving a distance of $ans[j]+x_1[i]+y_1[i]-x_2[j]-y_2[j],$ where both $x_2[j]\le x_1[i]$ and $y_2[j]\le y_1[i]$ must be satisfied.

Sort all springboard start and endpoints by $x$. Then for each $x_1[i]$ in increasing order we need to compute the minimum possible value of $ans[j]-x_2[j]-y_2[j]$ over all $j$ such that $x_2[j]\le x_1[i]$ and $y_2[j]\le y_1[i].$ Our approach requires some data structure $D$ that stores pairs and supports the following operations.

For each pair in increasing lexicographical order:

One candidate for $D$ is a segment tree that supports point updates and range minimum queries. A simpler approach is to use a map.

These operations run in $O(\log n)$ time amortized.

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);

const int MX = 1e5+5;

int N,P;
map<int,int> m;
int ans[MX];
void ins(int y, int v) {
	auto it = prev(m.upper_bound(y));
	if (it->s <= v) return;
	it ++;
	while (it != end(m) && it->s > v) m.erase(it++);
	m[y] = v;
int main() {
	cin >> N >> P; m[0] = 0;
	vector<pair<pair<int,int>,pair<int,int>>> ev;
	for (int i = 0; i < P; ++i) {
		pair<int,int> a,b; 
		cin >> a.f >> a.s >> b.f >> b.s;
		ev.push_back({a,{i,-1}}); // start point
		ev.push_back({b,{i,1}}); // end point
	for (auto& t: ev) {
		if (t.s.s == -1) {
			ans[t.s.f] = t.f.f+t.f.s+prev(m.upper_bound(t.f.s))->s;
		} else {
	cout << m.rbegin()->s+2*N;