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

问题描述

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

输入格式

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

输出格式

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

样例输入

1000
2
1 1 2 1
5 1 2 1

样例输出

5

数据范围

• $1 \le R \le 1,000,000$
• $0 < N \le 10000$