Diamond Theft
Contest: Educational Codeforces Round 156 (Rated for Div. 2)
Difficulty rating: 3300
Tags: data structures, greedy

Monocarp is the most famous thief in Berland. This time, he decided to steal two diamonds. Unfortunately for Monocarp, there are $$$n$$$ cameras monitoring the diamonds. Each camera has two parameters, $$$t_i$$$ and $$$s_i$$$. The first parameter determines whether the camera is monitoring the first diamond only ($$$t_i=1$$$), the second diamond only ($$$t_i=2$$$), or both diamonds ($$$t_i=3$$$). The second parameter determines the number of seconds the camera will be disabled after it is hacked.

Every second, Monocarp can perform one of the following three actions:

- do nothing;
- choose a camera and hack it; if Monocarp hacks the $$$i$$$-th camera, it will be disabled for the next $$$s_i$$$ seconds (if the current second is the $$$T$$$-th one, the camera will be disabled from the $$$(T+1)$$$-th to the $$$(T+s_i)$$$-th second, inclusive);
- steal a diamond if all cameras monitoring it are currently disabled. Monocarp cannot steal the second diamond if he hasn't stolen the first diamond yet.

Note that Monocarp can hack a camera multiple times, even if it is currently disabled.

Your task is to determine the minimum time it will take Monocarp to steal both diamonds, beginning with the first diamond, or report that it is impossible.

Input format:
The first line contains a single integer $$$n$$$ ($$$0 \le n \le 1500$$$) — the number of cameras.

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains two integers $$$t_i$$$ and $$$s_i$$$ ($$$1 \le t_i \le 3$$$; $$$1 \le s_i \le 2n$$$) — the parameters of the $$$i$$$-th camera.

Output format:
Print a single integer — the minimum time it will take for Monocarp to steal the first diamond first and then the second diamond. If it is impossible, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
2 6
1 2
1 2
2 1

Example output:
6

Example input:
4
2 8
3 2
3 2
3 5

Example output:
9

Editorial:
In this editorial, we will denote the number of cameras of type $$$i$$$ as $$$k_i$$$.
Without loss of generality, we can assume that our sequence of actions will look as follows:
• hack all cameras of type $$$1$$$, some cameras of type $$$2$$$ and all cameras of type $$$3$$$ in some order (let's call it the first block of actions);
• steal the first diamond;
• hack the remaining cameras of type $$$2$$$ and some cameras of type $$$3$$$ (the second block of actions);
• steal the second diamond.
Note that we don't hack the same camera of type $$$1$$$ or $$$2$$$ twice (this is just suboptimal), but some cameras of type $$$3$$$ will be hacked twice. We have to minimize the number of cameras of type $$$3$$$ which will be hacked twice.
Let's iterate on the number of actions we make after stealing the first diamond (denote it by $$$len$$$), and then iterate on the number of cameras of type $$$2$$$ in the first block (denote it by $$$i$$$). Then, the number of cameras of type $$$2$$$ we hack in the second block will be $$$k_2 - i$$$, and the number of cameras of type $$$3$$$ we hack in the second block is $$$len - (k_2 - i) - 1$$$. Since this is also the number of cameras of type $$$3$$$ we hack twice, we have to minimize this number. Note that the length of the first block is also fixed: it should be $$$k_1 + k_3 + i$$$.
Suppose we fixed which cameras of type $$$2$$$ and $$$3$$$ go to the second block, and which don't. For each block, we will store a special data structure that, for every $$$x$$$ from $$$0$$$ to the length of the block, calculates the value of $$$d_x - x$$$, where $$$d_x$$$ is the number of cameras which have to be hacked during the last $$$x$$$ actions in the block. Using something like Hall's theorem, we can prove that if every value of $$$d_x - x$$$ for every block is non-positive, there exists a way to hack all cameras in time. This can be efficiently modeled with a segment tree.
All cameras of type $$$1$$$ should be inserted into the data structure for the first block. For the cameras of type $$$2$$$, we either insert them into the second block, or insert them into the first block while subtracting $$$len$$$ from their values of $$$s_j$$$. For the cameras of type $$$3$$$, we either insert them into both blocks, or insert them into the first block while subtracting $$$len$$$ from their values of $$$s_j$$$.
Among all cameras of type $$$2$$$, which ones should belong to the first block, and which ones — to the second block? It's quite easy to see that the "longest" cameras of type $$$2$$$ should be in the first block. Unfortunately, with cameras of type $$$3$$$, it's a bit more tricky.
First, let's insert all cameras of type $$$1$$$ into the first block and all cameras of type $$$2$$$ into the blocks chosen for them. Then sort all cameras of type $$$3$$$ (in ascending order of their $$$s_j$$$ values) and use the following greedy approach: if a camera can be inserted into the first block after we subtract $$$len$$$ from its $$$s_j$$$, we insert it there; otherwise, we insert it into both blocks without subtraction. This greedy approach can be proved using something like exchange argument: if we skipped some camera which could be inserted into the first block, and chose some other camera for the same slot, they can be "swapped". So, all cameras of type $$$3$$$ are partitioned into two types.
After you've done inserting cameras into the respective blocks, check that everything's fine. This works in something like $$$O(n^3 \log n)$$$. Unfortunately, it is too slow.
To speed this up, let's use the following strategy: iterate on the value of $$$len$$$, then try solving the problem for $$$i=0$$$ (i. e. all cameras of type $$$2$$$ are initially in the second block). If it fails, we can try increasing $$$i$$$, shifting a camera of type $$$2$$$ from the second block to the first block and rebuilding the partition of cameras of type $$$3$$$, instead of starting it from scratch.
But how do we rebuild the partition of cameras of type $$$3$$$? We can use the following strategy. Store a set of cameras of type $$$3$$$ (sorted by their $$$s_j$$$) which are inserted only into the first block. While the first block is not OK (i. e. there exists some value of $$$x$$$ such that $$$d_x - x$$$ is positive), we will find the minimum $$$x$$$ such that $$$d_x - x$$$ is positive, and try to decrease it as follows: search for the camera of type $$$3$$$ which belongs only to the first block, has $$$s_j - len \le x$$$, and has the maximum $$$s_j$$$ among all such cameras. This is the camera which should be moved in the partition (i. e. instead of storing it in the first block, we store it in both blocks). Note that you might need to repeat this process (i. e. when you move a camera of type $$$2$$$ to the first block, it can force multiple cameras of type $$$3$$$ into the second block). Thus, our solution now works in $$$O(n^2 \log n)$$$.