题目描述

小 z 的手机电池电量有 $n$ 格 (满电)，每过 $1$ 小时电池的电量会减少 $1$ 格，手机电量最少为 $0$。小 z 把手机充满电之后出门了，出门时刻为 $0$ 时，在途中他经过了 $m$ 家 KFC，在时刻 $T$ 回到家。

小 z 在第 $i$ 家 KFC 停留的时间段为时刻 $l_i \sim r_i$。在 KFC 停留时，小 z 会给手机充电，这段时间里手机的电量每小时会增加 $1$ 格。手机电量最多为 $n$。

问小 z 回到家的时候，手机电量有几格?

数据范围： $1≤n≤10^9,1≤m<1000,1≤T<10^9$。

$0<l_1<r_1<l_2<r_2<…<l_m<r_m<T$。

输入格式

输入的第一行为 $3$ 个正整数 $n,m,T$，分别表示电池电量，KFC 店数目，小 z 回家的时刻。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，表示小 z 在第 $i$ 家 KFC 停留的时间段为 $l_i$ 到 $r_i$。

输出格式

1个整数，表示小 z 回到家时手机电量。

10 2 20
8 10
13 17

2

31 7 341
18 33 
63 67 
162 188 
207 227 
232 239 
258 295 
310 328

18

提示