### 问题描述 小蓝是个节俭而有品味的年轻人，每当他进入学校食堂，总是小心翼翼地选择着自己的菜肴。今天，他来到了一家新开的食堂，据说这里提供了各种美味的菜肴，而且还有一项特别的活动。 这家食堂共有 $k$ 种菜，每一种菜都有其独特的风味和口感。对于第 $i$ 种菜，价格是 $p_i$ 元每盘，而小蓝想要的份数是 $s_i$ 盘。不仅如此，食堂还举办了一个吸引人的活动：每购买 $2$ 盘同种菜，都会额外赠送一种异种菜。当然，小蓝**可以选择不接受赠送**的异种菜。 例如，食堂有 $3$ 种菜，小蓝可以每购买 $2$ 盘一号菜，可以选择赠送 $1$ 盘二号或者三号菜，同时，也可以选择不接受赠送。 **注意**，赠送的菜**不能**够参与买赠活动。 作为一个节俭的人，小蓝希望花费尽可能少的钱，但同时**也不能有任何冗余的菜肴**。他想知道，至少需要多少钱才能满足自己的需求。 ### 输入格式 本题包含多个测试样例： 第一行输入一个整数 $T$（ $1\leq T \le 200$），代表测试数据组数。 每组测试数据包含以下部分： 第一行包含一个整数 $k_t$（$1 \le k_t \le 50$），表示食堂提供的菜肴种类数。 接下来 $k_t$ 行，每行包含两个整数 $p_i$ 和 $s_i$（$1 \le s_i \le 100, \sum\limits_{i=1}^{k_t} s_i \le 300, 1 \le p_i \le 10^5$），表示第 $i$ 种菜的价格每盘和小蓝想要的份数。 保证所有测试组的 $s_i$ 之和不超过 $2000$，即 $\sum\limits_{t=1}^T \sum\limits_{i=1}^{k_t} s_i \leq 2000$。 ### 输出格式 对于每组测试样例，输出一行，包含一个整数，表示小蓝至少需要花费多少钱才能满足自己的需求。 ### 样例输入 ```bash 1 3 5 2 6 3 4 1 ``` ### 样例输出 ```bash 22 ``` ### 说明 一种购买方案为： 买 $2$ 盘一号菜，送 $1$ 盘二号菜。 买 $2$ 盘二号菜，送 $1$ 盘三号菜。 费用为 $22$ 元。