Artist

Seungwon, better known by the pen name 'Nam Nam Seo', is an artist famous all over the world. Nobody else works the way he does, and every exhibition he opens fills up until there is no room left to stand.

Right now there are $N$ blocks in Seungwon's studio. He will pick exactly $K$ of them and build a new piece. He glues the chosen blocks from the lower left to the upper right so that they touch corner to corner, and he mounts the result on a canvas that fits it exactly.

A perfect piece matters a great deal to Seungwon, so he places every block parallel to the edges of the canvas, and he never swaps a block's width and height. That is, if the chosen blocks have widths and heights ($w_1$, $h_1$), ($w_2$, $h_2$), $\cdots$, ($w_K$, $h_K$), the canvas he needs has size ($w_1 + w_2 + \cdots + w_K$) $\times$ ($h_1 + h_2 + \cdots + h_K$).

Seungwon wants the area of the canvas to be as small as possible. His art may be beyond us, but computing the minimum area of the canvas is not. Help him finish the piece.

The first line contains the number of blocks Seungwon owns, $N$ ($1 \le N \le 3000$), and the number of blocks he will use, $K$ ($1 \le K \le N$), separated by a space.

Each of the next $N$ lines contains the width $w_i$ and the height $h_i$ of one block, separated by a space. ($1 \le w_i$, $1 \le h_i$, and the sum of all $w_i$ and the sum of all $h_i$ are each at most $10^9$.)

Print the minimum area of the canvas on the first line.