#p407. 例题7.2.4 饥饿的奶牛

例题7.2.4 饥饿的奶牛

题目描述

牛在饲料槽前排好了队。饲料槽依次用11到NN(1<=N<=2000)(1<=N<=2000)编号。每天晚上,一头幸运的牛根据约翰的规则,吃其中一些槽里的饲料。

约翰提供BB个区间的清单。一个区间是一对整数start−endstart-end,1<=start<=end<=N1<=start<=end<=N,表示一些连续的饲料槽,比如1−31-3,7−87-8,3−43-4等等。牛可以任意选择区间,但是牛选择的区间不能有重叠。

当然,牛希望自己能够吃得越多越好。给出一些区间,帮助这只牛找一些区间,使它能吃到最多的东西。

在上面的例子中,1−31-3和3−43-4是重叠的;聪明的牛选择1−3,7−8{1-3,7-8},这样可以吃到55个槽里的东西。

输入格式

第一行一个整数BB,表示奶牛的组数。(1<=B<=1000)(1<=B<=1000)

第2 n+12~n+1行,每行两个整数startstart和endend,描述了一组奶牛提出的请求。

输出格式

一个整数,表示最多有多少个食桶可以被食用。

样例数据

input


3

1 3

7 8

3 4



output


5

(满足第1组和第2组奶牛的要求,这样1~3号和7~8号这5个食桶可以被食用)

数据规模与约定

时间限制:1s1 \text {s}

空间限制:256MB256 \text {MB}