The cows are so modest they want Farmer John to install covers around the circular corral where they occasionally gather. The corral has circumference C (1 <= C <= 1,000,000,000), and FJ can choose from a set of M (1 <= M <= 100,000) covers that have fixed starting points and sizes. At least one set of covers can surround the entire corral. Cover i can be installed at integer location x\_i (distance from starting point around corral) (0 <= x\_i < C) and has integer length l\_i (1 <= l\_i <= C). FJ wants to minimize the number of segments he must install. What is the minimum number of segments required to cover the entire circumference of the corral? Consider a corral of circumference 5, shown below as a pair of connected line segments where both '0's are the same point on the corral (as are both 1's, 2's, and 3's). Three potential covering segments are available for installation: Start Length i x\_i l\_i 1 0 1 2 1 2 3 3 3 0 1 2 3 4 0 1 2 3 ... corral: +---+---+---+---+--:+---+---+---+- ... 11111 1111 22222222 22222222 333333333333 |..................| As shown, installing segments 2 and 3 cover an extent of (at least) five units around the circumference. FJ has no trouble with the overlap, so don't worry about that. 奶牛们非常羞涩，他们要求Farmer John在他们的圆形牛棚周围建造围栏。牛棚的周长为c(1 <= C <= 1,000,000,000)，现在，FJ希望从一些有固定起点和终点的栏杆的集合里选出一些栏杆。栏杆i 的起点可以被建造在一个整数位置 x\_i(相距围栏起点i个长度) (0 <= x\_i < C),并且，这个栏杆有一个整数长度l\_i(1 <= l\_i <= C)。 FJ 希望最小化栏杆的数量，从而达到覆盖整个牛棚的外圈。

P2980 [USACO10FEB] Covering the Corral G

题目描述

输入格式

输出格式