아티스트

'남남서'라는 예명으로 더 유명한 승원이는 세계적으로 유명한 아티스트다. 작품 세계가 타의 추종을 불허해서, 전시회가 열릴 때마다 사람이 꽉 차 발 디딜 틈이 없다.

지금 승원이의 작업실에는 블록이 $N$개 놓여 있다. 승원이는 이 블록 중에서 정확히 $K$개를 골라 새 작품을 만든다. 고른 블록은 왼쪽 아래에서 오른쪽 위로 꼭짓점끼리 맞닿게 이어 붙이고, 그 전체를 꼭 맞는 캔버스에 올린다.

승원이는 완벽한 작품을 매우 중요하게 여겨서 모든 블록을 캔버스의 모서리와 평행하게 놓고, 가로와 세로를 바꿔 놓지도 않는다. 즉 고른 블록의 가로와 세로 길이가 각각 ($w_1$, $h_1$), ($w_2$, $h_2$), $\cdots$, ($w_K$, $h_K$)일 때 필요한 캔버스는 ($w_1 + w_2 + \cdots + w_K$) $\times$ ($h_1 + h_2 + \cdots + h_K$) 크기다.

승원이는 캔버스의 넓이를 가능한 한 작게 하고 싶어 한다. 심오한 승원이의 작품 세계는 우리가 이해할 수 없어도, 캔버스의 최소 넓이를 구하는 것만큼은 우리도 해낼 수 있다. 승원이가 작품을 완벽하게 만들도록 도와주자.

첫째 줄에 승원이가 가진 블록의 수 $N$ ($1 \le N \le 3000$)과 작품에 쓸 블록의 수 $K$ ($1 \le K \le N$)가 공백을 사이에 두고 주어진다.

다음 $N$개의 줄에는 각 블록의 가로 길이 $w_i$와 세로 길이 $h_i$가 공백을 사이에 두고 주어진다. ($1 \le w_i$, $1 \le h_i$이고, $w_i$의 합과 $h_i$의 합은 각각 $10^9$ 이하)

첫째 줄에 캔버스의 최소 넓이를 출력한다.