Informatica Online Judge

  아티스트 [2163 / 0873]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net(33rd 김동현)]

Background

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

지금 승원이의 작업실에는 블록이 N개 놓여 있다. 승원이는 이 블록들 중 정확히 k개를 사용해 새로운 작품을 만들려고 한다. 승원이는 이 블록들을 왼쪽 아래에서 오른쪽 위로, 꼭짓점끼리 맞닿게 배치하여 꼭 맞는 캔버스 위에 붙일 것이다.

승원이는 완벽한 작품을 매우 중요시하기 때문에 모든 블럭을 캔버스의 모서리와 평행하게 배치할 것이며, 가로와 세로를 바꿔 배치하지도 않을 것이다. 즉, 고른 블럭들의 가로와 세로 길이가 각각 (w1, h1), (w2, h2), ⋯, (wk, hk)일 때 필요한 캔버스는 (w1+w2+⋯+wk) × (h1+h2+⋯+hk) 크기라는 것이다.

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

Input

첫 번째 줄에는 승원이가 가진 블록의 수 N (1≤N≤3000) 과 작품에 쓸 블록의 수 K (1≤K≤N) 가 주어진다.

다음 N개의 줄에는 각 블록의 가로 길이 wi와 세로 길이 hi가 공백을 사이에 두고 주어진다. (wi들의 합과 hi들의 합은 각각 109 이하)

Output

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

IO Example

입력
5 2
1 5
2 3
4 2
6 3
3 2

출력
24

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]