### 问题描述 暑期降至，小蓝最近决定将家里重新翻修一遍，她准备先从粉刷栅栏开始。 小蓝家有一个长度为 $n$ 的栅栏，起点记为坐标 $0$ ，现在小蓝想要将栅栏重新粉刷一遍。小蓝现在可以对栅栏粉刷 $q$ 次，每次可以将 $[l,r]$ 区间内的栅栏粉刷一遍。小蓝按顺序记下了她粉刷 $q$ 次的区间，她现在想知道她最少粉刷几次时把栅栏粉刷了至少一半。 若小蓝可以在 $q$ 次粉刷结束之前把栅栏粉刷一半，则输出小蓝最少需要粉刷到第几次可以将栅栏粉刷至少一半，否则输出 $-1$ 。 ### 输入格式 第一行两个正整数 $n,q$ ，代表栅栏的长度和粉刷次数。 接下来 $q$ 行，每行两个整数表示当前粉刷的区间。 ### 输出格式 输出一行一个整数。 ### 样例输入 ```txt 6 3 0 1 4 6 4 5 ``` ### 样例输出 ```txt 2 ``` ### 说明 在第一次粉刷区间 $[0,1]$ 之后，粉刷的栅栏的长度为 $1$ 。 在第二次粉刷区间 $[4,6]$ 之后，粉刷的栅栏的长度为 $1+2=3$ 。此时被粉刷的栅栏的长度为总长度的一半，所以小蓝粉刷两次时，栅栏已经被粉刷了至少一半。 ### 评测数据规模 对于 $50$% 的评测数据 $1 \leq n , q\leq 10^{3} , 0 \leq l \leq r \leq n $ 。 对于 $100$% 的评测数据 $1 \leq n , q \leq 10 ^{5} , 0 \leq l \leq r \leq n $ 。