1966: [USACO 2022 US Open Contest Gold] Problem 1. Apple Catching
题目描述
It's raining apples! At certain points in time, some number of apples will hit the number line. At certain points in time, some of Farmer John's cows will arrive on the number line and start catching apples.
If an apple hits the number line without a cow to catch it, it is lost forever. If a cow and an apple arrive at the same time, the cow catches it. Each cow can travel one unit per second. Once a cow catches a single apple, she exits the number line.
If FJ's cows collaborate optimally, how many apples can they catch in total?
输入
The next lines each contain four integers , , , and ()
- If , this means that of FJ's cows arrive on the number line at time at location .
- If , this means that apples will hit the number line at time at location .
It is guaranteed that all of the ordered pairs are distinct.
输出
样例输入
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6样例输出
10提示
In this example, none of the apples that land at time may be caught. Here is a way for apples to be caught:
- All six of FJ's cows that arrive at time catch one of the apples that land at time .
- One of FJ's cows that arrive at time catches one of the apples that land at time .
- Three of the remaining cows that arrive at time catch one of the apples that land at time .
SAMPLE INPUT:
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6
SAMPLE OUTPUT:
9
Here again, none of the apples that land at time may be caught. Furthermore, none of the cows that arrive at time may catch any of the apples that land at time . Here is a way for apples to be caught:
- All six of FJ's cows that arrive at time catch one of the apples that land at time .
- Three of the remaining cows that arrive at time catch one of the apples that land at time .