GJX卖鸡排

题号：NC54285
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众所周知，GJX多才多艺，会唱跳、RAP、做鸡排。

鉴于之前参加商业竞赛并没有赚到什么钱，所以他决定卖鸡排。

GJX一口气制作了N个鸡排，设第i个鸡排的价格为 $p_i$ 。

由于舍友经常趁他卖鸡排的时候偷吃他做的鸡排，所以他决定每天只拿出一个鸡排来卖。

但我们都知道，鸡排是有保质期的，设第i个鸡排的保质期最后一天为 $d_i$ 。善良的GJX是不会卖过期的鸡排的。

GJX一下子就想出了能赚到最多钱的卖鸡排方案，聪明的你也一定知道吧！

输入包含多组测试样例。

第一行给出一个正整数 $T(1\leq T\leq100)$ ，表示T组数据。

每组数据第一行给出正整数N，表示有N个鸡排。

接下来N行，每行给出两个正整数 $p_i$ 和 $d_i$ ，表示第i个鸡排的价格和保质期的最后一天。

一行，一个整数，表示GJX最多能赚多少钱。

示例1

复制

复制

GJX首先在第1天卖出30元的鸡排，然后在第2天卖出50元的鸡排。