暂无测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

平面上有一个大矩形，其左下角坐标 \((0,0)\)，右上角坐标 \((R,R)\)。
大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。
所有矩形的顶点都是整点。
要求画一根平行于 \(y\) 轴的直线 \(x=k\)（\(k\) 是整数) ，
使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。
并且，要使得大矩形在直线左边的的面积尽可能大。
注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。

输入

第一行是整数 \(R\)，表示大矩形的右上角坐标是 \((R,R)\)。

接下来的一行是整数 \(N\),表示一共有 \(N\) 个小矩形。
再接下来有 \(N\) 行。
每行有 \(4\) 个整数，\(L\),\(T\),\(W\) 和 \(H\),
表示有一个小矩形的左上角坐标是 \((L,T)\),宽度是 \(W\)，高度是 \(H\)。
小矩形不会有位于大矩形之外的部分。

输出

输出整数 \(n\)，表示答案应该是直线 \(x=n\)。
如果必要的话，\(x=R\) 也可以是答案。

样例输入

1000
2
1 1 2 1
5 1 2 1

样例输出

5

数据范围限制

\(1 \leq R \leq 10^6\),\(0 < N \leq 10^4\),\(0 \leq L,T \leq R\),\(0 < W,H \leq R\)。

来源

入门篇练习5.3.9