You are given a circular knapsack and items, each with a value and a beauty score. The items are numbered from
to
. The
-th item has a value
and a beauty score
. The knapsack can hold exactly
items arranged in a circle, meaning that if the selected items are numbered from
to
, the item
is adjacent to the item
and the item
.
The overall beauty value of the knapsack is defined as:
where the overall beauty value of the knapsack is the sum of the item's value minus the absolute difference of the beauty score between the current item with the next adjacent item.
Your task is to help Bob maximize the overall beauty value of the knapsack.
Input Specification
The first line of input contains two integers, and
(
), indicating the number of given items and the number of items the knapsack can hold.
Each of the following lines contains two integers
and
(
), indicating the value and the beauty score of the
th item.
Output Specification
Output one integer, the max overall beauty value of the knapsack.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
No additional constraints. |
Sample Input
5 3
2 1
4 2
6 4
8 8
10 16
Sample Output
6
Explanation
Bob can put items ,
and
in a circle, and the overall beauty value is
, which is the max possible value.
Comments