工程
有n个工人做两个工程A和B，每个工程都被分为相同的m份，给你第i个工人做A中的一份需要的时间Xi秒，和做B中的一份所需时间Yi秒，问最短需要多少时间可以完成这两项工程。
Input
第一行是一个整数t (1 <= t <= 100),表示有t组测试数据;
每组测试数据第一行有两个整数 n (1 <= n <= 100), m (1 <= m <= 100).
接下来的n行,每行有两个整数Xi,Yi;
每组测试数据第一行有两个整数 n (1 <= n <= 100), m (1 <= m <= 100).
接下来的n行,每行有两个整数Xi,Yi;
Output
输出最短时间，占一行。
Sample Input
1
3 20
1 1
2 4
1 6
Sample Output
18