P2157 [SDOI2009] School Canteen

Xiao F’s school is in a remote corner of the city, so all students have to eat at school. The school has a canteen which, although simple, always serves dishes that satisfy the students. Of course, people have different tastes, but each person’s taste can be represented by a non-negative integer. Due to limited staff, the canteen can only cook for one person at a time. The time to cook each dish depends on the previous one: if the previous dish has taste $a$ and the current dish has taste $b$, then the time needed to cook this dish is $(a\operatorname{or}b)-(a\operatorname{and}b)$, and no time is counted for the first dish. Here, $\operatorname{or}$ and $\operatorname{and}$ denote bitwise OR and bitwise AND on integers, corresponding to the C language operators `|` and `&`. There are many students in this school, so cooking often takes a lot of time. Therefore, the canteen may sometimes deviate from the original queue order to shorten the total dining time. Although students can understand this practice, everyone has a certain tolerance. Specifically, the $i$-th student in the queue allows at most the $B_i$ people immediately behind them to be served before them. If any student beyond those $B_i$ immediately behind is served earlier than the $i$-th student, the $i$-th student will be very angry. Thus, the canteen also needs to take students’ emotions into account. Now, under the premise of satisfying everyone’s tolerance, Xiao F wants to know the minimum total time needed for the school canteen to finish all the dishes.

The first line contains a positive integer $C$, the number of test cases. For each test case, the first line contains a positive integer $N$, the number of students. Starting from the second line of each test case, there are $N$ lines. Each line contains two space-separated non-negative integers $T_i$ and $B_i$, representing, in queue order from front to back, each student’s required dish taste and their tolerance. There are no extra blank lines between test cases.

Output $C$ lines, each containing one integer, the minimum total time for the canteen to finish all dishes for the corresponding test case.

For the first test case: - Student 1 allows Student 2 or Student 3 to be served before them; Student 2 allows Student 3 to be served before them; Student 3 is strict and must be served before any student behind them. - One optimal order is to cook for Students 3, 2, 1, 4, 5. The time for each dish is respectively $0$, $8$, $1$, $6$, and $1$. Constraints: - For $30\%$ of the testdata, $1 \le N \le 20$. - For $100\%$ of the testdata, $1 \le N \le 1000$, $0 \le T_i \le 1000$, $0 \le B_i \le 7$, $1 \le C \le 5$. - For $30\%$ of the testdata, $0 \le B_i \le 1$. - For $65\%$ of the testdata, $0 \le B_i \le 5$. - For $45\%$ of the testdata, $0 \le T_i \le 130$. Translated by ChatGPT 5