#1919. 分糖果 暂未评定

题目背景

到了学期末，在幼儿园工作的刘老师要为自己所带班级的小朋友分发糖果。

题目描述

刘老师的班上共有 名小朋友，第 位小朋友对糖果的喜爱程度为 ，他在本学 期的表现评分为 。刘老师分配糖果的方法如下：

1. 以某个顺序安排这 位小朋友排成一排，刘老师从头到尾逐一分配糖果。

2. 队伍中的第 位小朋友至少获得的糖果数量为前 位小朋友对糖果的喜爱程度之和。

3. 由于第 位小朋友可以看见第 位小朋友获得的糖果数量，为了不让第 位小朋友觉得不公平，刘老师保证第 i 位小朋友获得的糖果不少于第 位小朋友。

4. 在为第 位小朋友分配完糖果后，刘老师将额外再奖励第 位小朋友数量为 的糖果。我们设第 位小朋友获得的糖果数量为 ，形式化地讲：

第一行包含一个正整数 ，表示测试数据的组数。

接下来描述这 组测试数据，每组数组的第一行包含一个正整数 ，表示刘老师班上小朋友的数量。

每组数据接下来 行中，每行两个正整数，分别为 和 ，含义如问题描述中所述。

共 行，每行包含一个整数， 表示被分配到最多糖果的那位小朋友最少获得的糖果数量。

样例输入 1

1
3
4 1
2 2
1 2

样例输出 1

8

样例输入 2

1
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

样例输出 2

902

next_permutation: 分

玄学贪心： 分

贪心： 分