7473: USACO 2022 US Open Contest, Gold —— T1 Apple Catching
[Creator : ]
Description
天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。
如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。
如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？
如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？
Input
输入的第一行包含 $N\ (1≤N≤2⋅10^5)$，为苹果落到数轴上的次数或 FJ 的奶牛出现的次数。
以下 $N$ 行每行包含四个整数 $q_i,t_i,x_i,n_i\ (q_i \in \{1,2\},\ 0≤t_i≤10^9,\ 0≤x_i≤10^9,\ 1≤n_i≤10^3)$。
- 如果 $q_i=1$，意味着 FJ 的 $n_i$ 头奶牛在 $t_i$ 时刻来到数轴上的 $x_i$ 位置。
- 如果 $q_i=2$，意味着 $n_i$ 个苹果在 $t_i$ 时刻落到了数轴上的 $x_i$ 位置。
Output
输出 FJ 的奶牛总计能接住的苹果的最大数量。
Sample 1 Input
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6
Sample 1 Output
10
在这个例子中，在 $t=5$ 时刻落地的 $100$ 个苹果均不能被接住。以下是一种接住 $10$ 个苹果的方式：
- FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。
- FJ 的一头 $t=2$ 时刻到达的奶牛接一个 $t=8$ 时刻落地的苹果。
- 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。
Sample 2 Input
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6
Sample 2 Output
9
再一次地，在 $t=5$ 时刻落地的苹果均不能被接住。除此之外，在 $t=2$ 时刻到达的奶牛均不能接住 $t=8$ 时刻落地的苹果。以下是一种接住 $9$ 个苹果的方式：
- FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。
- 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。