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?

 

天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。

如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。

如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？

 

The maximum number of apples FJ's cows may collectively catch.

In the first example, none of the 100 apples that land at time t=5 may be caught. Here is a way for 10 apples to be caught:

* All six of FJ's cows that arrive at time t=4 catch one of the apples that land at time t=8.
* One of FJ's cows that arrive at time t=2 catches one of the apples that land at time t=8.
* Three of the remaining cows that arrive at time t=2 catch one of the apples that land at time t=6.

 

In the second example, none of the apples that land at time t=5 may be caught. Furthermore, none of the cows that arrive at time t=2 may catch any of the apples that land at time t=8. Here is a way for 9 apples to be caught:

* All six of FJ's cows that arrive at time t=4 catch one of the apples that land at time t=8.
* Three of the remaining cows that arrive at time t=2 catch one of the apples that land at time t=6.

USACO 2022 US Open Contest, Gold