15310번 - 아티스트

'남남서'라는 예명으로 더 유명한 승원이는 세계적으로 유명한 Artist이다. 그의 작품 세계는 타의 추종을 불허하며, 열리는 전시회마다 사람들로 꽉 차 발 디딜 틈이 없을 정도이다.

지금 승원이의 작업실에는 블록이 $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 3\, 000$) 과 작품에 쓸 블록의 수 $K$ ($1 \le K \le N $) 가 주어진다.

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

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