分发糖果

题目描述

幼儿园有 n 名小朋友，第 i 位喜爱程度为 a_i，表现评分为 b_i。按某种顺序排队逐一分配糖果，第 i 位获得 c_i = max(c_{i-1}, 前 i 位 a 之和) + b_i。安排顺序使最大 c_i 最小。

输入格式

第一行正整数 T。每组数据第一行 n，接下来 n 行每行 a_i 和 b_i。

输出格式

T 行，每行一个整数表示答案。

样例输入 #1

1
3
4 1
2 2
1 2

样例输出 #1

8

样例说明 #1

按 3,2,1 顺序领取时，最多糖果数量为 8。

数据范围

对于 100% 的数据，$1\leq n\leq 5\times10^4$，$T\leq 10$。

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布