Background

Special for beginners, ^_^

Description

你毕业了，有很多书需要快递。 可以把书放到盒子里，每个盒子快递费用的高度和宽度的乘积。总费用就是所有单个盒子的费用之和。 装盒子时，书的顺序不能交换，然后书必须按照架子上的方向装（不能旋转90度）。 问最少需要多少快递费。

Format

Input

第一行两个正整数n（不超过1000）和k，分别表示书的数量和盒子的数量。 接下来n行，按照书架上的顺序给出每本书的尺寸，每行两个数，分别表示书的宽度和高度（宽度高度不超过1e6）。

Output

输出最小快递费用。

Samples

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

138

Limitation

1s, 1024KiB for each test case.

#hint 对于样例1 总共需要2个盒子： 盒子1: (3 + 4 + 1) * 12 = 96 盒子2: (6 + 1) * 6 = 42 总共: 96 + 42 = 138