题目描述

光头强在周末的时候经常购物来犒劳自己。

某个周末，光头强在到商场购物得知商场正在举行活动：用手机的banana pay付款能以更“优惠”的价格买到 $k$ 个商品。

然而banana pay并不是一个良心电商，用banana pay支付某些商品的价格会变便宜，但是某些商品的价格会变贵。

光头强告诉你 $N$ 个商品分别用banana pay支付的价格和用现金支付的价格，请你帮它算算最少用多少元能买下来全部的 $N$ 个商品？

输入格式

输入的第一行为一个正整数 $T(1\leq T \leq 20)$ ,代表测试数据的组数。

在 $T$ 组数据中，每组数据的第 $1$ 行是两个正整数 $N(1\leq N \leq 10000)$ 和 $k(0\leq k\leq N)$ ，含义如题面所述。

接下来 $N$ 行每行有两个正整数 $a$ 和 $b$ ，分别代表该商品用banana pay支付的价格和用现金支付的价格。 $(0\leq a,b\leq 100000)$

对于每组数据输出一个正整数，代表光头强最少需要花费的金额，每组输出占一行。