食堂排队 (canteen)

• 输入：canteen.in
• 输出：canteen.out
• 时间限制：2 s
• 内存限制：256 MB

题目描述

训练营食堂每天中午都会排起长队。队伍中共有 $n$ 名同学，从前到后编号为 $1$ 到 $n$。

第 $i$ 名同学想吃的菜可以用一个非负整数 $t_i$ 表示。食堂每次只能给一名同学出餐。

如果上一份菜的编号为 $x$，当前这份菜的编号为 $y$，那么当前这份菜需要额外花费 $x\operatorname{xor}y$ 的时间。第一份菜不需要额外花费时间。

为了减少总等待时间，食堂可以不完全按照队伍顺序出餐。但是每名同学都有自己的忍耐度 $b_i$：第 $i$ 名同学最多允许他身后紧接着的 $b_i$ 名同学先拿到餐。

换句话说，如果某个编号大于 $i+b_i$ 的同学在第 $i$ 名同学之前拿到餐，那么第 $i$ 名同学就会生气。

请你求出，在不让任何同学生气的前提下，食堂给所有同学出完餐的最小总时间。

输入格式

从文件 canteen.in 中读入数据。

第一行包含一个整数 $C$，表示数据组数。

对于每组数据：

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含两个整数 $t_i,b_i$，分别表示第 $i$ 名同学想吃的菜和忍耐度。

输出格式

输出到文件 canteen.out 中。

对于每组数据，输出一行一个整数，表示最小总时间。

样例1输入

1
5
9 2
8 1
0 0
15 1
14 0

样例1输出

16

样例1解释

一种最优出餐顺序为 $3,2,1,4,5$。

这 $5$ 份菜依次产生的额外时间为 $0,8,1,6,1$，总时间为 $16$。

在这个顺序中，第 $1$ 名同学允许第 $2,3$ 名同学先拿到餐，第 $2$ 名同学允许第 $3$ 名同学先拿到餐，因此不会有人生气。

数据范围

对于所有数据，$1 \le C \le 5$，$1 \le n \le 1000$，$0 \le t_i \le 1000$，$0 \le b_i \le 7$。每个测试点 $5$ 分。