e-olymp
Competitions

2018 USACO January

Lifeguards (Bronze)

Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires n cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time t = 0 until time t = 1000 on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time t = 4 and ending at time t = 7 covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired 1 more lifeguard than he has the funds to support. Given that he must fire exactly one lifeguard, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

Input

The first line contains n (1n100). Each of the next n lines describes a lifeguard in terms of two integers in the range 0...1000, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

Output

Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires 1 lifeguard.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
5 9
1 4
3 7
Output example #1
7
Input example #9
85
204 214
328 335
407 415
493 504
53 61
436 445
447 456
530 541
379 392
47 55
85 96
403 410
182 194
73 82
501 512
539 550
315 325
254 267
306 317
105 115
35 43
568 580
370 383
93 102
245 258
58 69
442 450
363 374
349 355
99 108
394 405
11 20
27 37
555 564
200 207
112 122
142 152
130 138
119 131
263 274
219 229
471 483
156 169
413 424
517 528
338 350
211 221
353 360
286 296
459 467
79 89
590 602
332 342
190 202
233 241
167 174
422 431
278 287
66 77
135 144
177 185
430 439
390 397
201 250
239 249
227 235
357 366
455 461
294 302
526 533
272 282
546 557
480 488
150 160
40 49
19 29
171 180
464 474
510 520
485 495
561 571
300 309
323 330
585 593
579 588
Output example #9
591
Source 2018 USACO January, Bronze