## Circular Knapsack Problem

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

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.

.

#### 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.