|
||||||||||
长期素食Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 311 Accepted Submission(s): 76 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
Sample Output
Source | ||||||||||
|