#PU972. USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters
USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters
USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters
题目描述
Farmer John has cows, conveniently labeled , who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked pies (), labeled . Cow enjoys pies with labels in the range (from to inclusive), and no two cows enjoy the exact same range of pies. Cow also has a weight, , which is an integer in the range . Farmer John may choose a sequence of cows after which the selected cows will take turns eating in that order. Unfortunately, the cows don't know how to share! When it is cow 's turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval . Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight () of a sequence for which each cow in the sequence eats at least one pie.
输入格式
The first line contains two integers and . The next lines each describe a cow in terms of the integers , and .
输出格式
Print the maximum possible total weight of a valid sequence.
数据范围
Test cases 2-5 satisfy and . Test cases 6-9 satisfy
样例
样例 1
2 2
100 1 2
100 1 1
200
In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However,
if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.
Problem credits: Benjamin Qi