F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

长期素食

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
1 4 6 10 1 7 2 2 3 9 1
 

Sample Output
86
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-10 12:30:42, Gzip enabled