题目描述

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

输入格式

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

接下来的一行是整数$N$，表示一共有$N$个小矩形($0 < N \leq 10,000$)。

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

输出格式

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

输入样例

1000
2
1 1 2 1
5 1 2 1

输出样例

5