长期素食

Problem Description

Mutsumi 是一名素食主义者。为了保持长期素食，她准备在接下来的 $k$ 天中只吃自己种的黄瓜。 Mutsumi 有 $n$ 片黄瓜田，编号从 $1$ 到 $n$。在接下来 $k$ 天中的每一天，她都会选择一片黄瓜田，收获其中的黄瓜。如果她在第 $i$ 天选择了编号为 $j$ 的黄瓜田，她会获得 $a_j + i \times b_j$ 点幸福值。为了保证黄瓜的正常生长，她不会连续两天选择同一片黄瓜田。 Mutsumi 想知道她在 $k$ 天中获得的幸福值之和的最大值。

Input

输入包含多组测试数据： 输入的第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试数据的组数。 对于每组测试数据： 第一行包含两个整数 $n$, $k$ ($2 \le n, k \le 10^5$)，表示 Mutsumi 拥有的黄瓜田数量和总天数。 接下来 $n$ 行，第 $i$ 包含两个整数 $a_i$, $b_i$ ($1 \le a_i \le 10^9, 1 \le b_i \le 10^4$)，具体含义见题面。

Output

对于每组测试数据： 输出一行一个整数，表示 Mutsumi 在 $k$ 天中获得的幸福值之和的最大值。

Sample Input

1
4 6
10 1
7 2
2 3
9 1

Sample Output

86

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）