Mutsumi 是一名素食主义者。为了保持长期素食，她准备在接下来的 $k$ 天中只吃自己种的黄瓜。

Mutsumi 有 $n$ 片黄瓜田，编号从 $1$ 到 $n$。在接下来 $k$ 天中的每一天，她都会选择一片黄瓜田，收获其中的黄瓜。如果她在第 $i$ 天选择了编号为 $j$ 的黄瓜田，她会获得 $a_j+i \times b_j$ 点幸福值。为了保证黄瓜的正常生长，她不会连续两天选择同一片黄瓜田。

Mutsumi 想知道她在 $k$ 天中获得的幸福值之和的最大值。

输入包含多组测试数据：

输入的第一行包含一个整数 $T (1≤T≤20)$，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 $n, k (2≤n,k≤10^5 )$，表示 Mutsumi 拥有的黄瓜田数量和总天数。

接下来 $n$ 行，第 $i$ 包含两个整数 $a_i,b_i (1≤a_i ≤10^9,1≤b_i ≤10^4 )$，具体含义见题面。

对于每组测试数据：

输出一行一个整数，表示 Mutsumi 在 $k$ 天中获得的幸福值之和的最大值。