410295: GYM104003 C William and Middle Management

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. William and Middle Managementtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

William is employed at a local factory in his dream job: middle management.

Taking the assembly line to heart, the factory contains $$$N$$$ workers, who reside on a line. Each individual $$$i$$$ has a productivity $$$p_i$$$ and works $$$h_i$$$ hours. Their individual output is given by the product of these two values.

As he is the most senior middle manager, William gets the first pick of his team. William is expected to manage a team of $$$K$$$ people and his bonus is the total output of his managed workers, in dollars. Of course, the team must be contiguous to ensure sufficient team bonding.

Please help William determine the optimal team and more importantly, tell him what he truly cares about, his bonus.

Input

The first line contains two integers: $$$N$$$ and $$$K$$$ where $$$1 \leq K \leq N \leq 10^5$$$.

The next $$$N$$$ lines each contain two integers, $$$1 \leq p_i \leq 100$$$ and $$$1 \leq h_i \leq 100$$$.

Output

A single integer, William's optimal bonus.

ExampleInput
4 2
2 3
1 3
3 2
4 1
Output
10

加入题单

算法标签: