P83890

饥饿的奶牛

难度 6 级 动态规划 线性
讨论 统计 2通过 2提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。

现用汉语翻译为:

有 N 个区间,每个区间 x,y 表示提供的 x\sim y 共 y-x+1 堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。

输入

第一行一个整数 N。

接下来 N 行,每行两个数 x,y,描述一个区间。

输出

输出最多能吃到的牧草堆数。

样例

样例 1
输入
3
1 3
7 8
3 4
输出
5

提示

1 \leq n \leq 1.5 \times 10^5,0 \leq x \leq y \leq 3 \times 10^6。

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交