输入描述:

The first input line contains two integers: n (1 ≤ n ≤ 1000), representing the number of books, andk(1 ≤k≤n), representing the number of boxes to put the books in. The followingninput lines contain the dimensions of the books, one book per line, in the order they appear on the shelf, from left to right. The ith of these input lines contains two integers,wi (1 ≤wi ≤ 106) andhi (1 ≤hi ≤ 106), representing (respectively) the width and height of the ith book on the shelf from the left.

输出描述:

On a line by itself, print the minimum cost of boxing the books.

5 2
3 10
4 7
1 12
6 4
1 6

138

Putting the first three books in one box and the last two books in the second box will result in the minimum cost.
 
Box1: (3 + 4 + 1) * 12 = 96
Box2: (6 + 1) * 6 = 42
Total: 96 + 42 = 138

5 5
2 6
1 8
3 4
2 12
3 9

83

备注: