Background

Special for beginners, ^_^

Description

某校建了一个新的校区，要把图书馆整个搬迁到新校区，并保证图书的顺序不发生错乱。 图书一般是按照中图分类号升序排列的，所以图书管理员在搬家时不允许交换任意两本书的位置。 我们假设每本书是立在书架上的，有高度和宽度，为了保护书的安全，需要把书竖着装进高度和宽度为某个值的盒子中，这个保护盒不允许旋转90度（即高度和宽度互换）。每个盒子搬运费用为高度和宽度的乘积。总费用就是所有单个盒子的费用之和。问最少需要多少快递费能完成一排书的装运。

Format

Input

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

Output

输出最小快递费用。

Samples

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

138

Limitation

1s, 1024KiB for each test case.