Kisik

은하 간 국가들의 식민 동맹(CAIN)은 화성에 K개의 가족을 위한 마을을 세우기로 했다. 따라서 가족마다 건물을 하나씩, 모두 K개의 건물을 지어야 한다. 각 가족에게는 우주 최고의 건축가들이 준비한 N가지 건물 설계 중 하나가 배정된다. 모든 건물은 직사각형이고, i번째 건물의 너비는 Wi, 높이는 Hi이다. 또한 CAIN이 장려하는 다양성을 위해 모든 가족은 서로 다른 설계를 받는다.

건물들은 서로 붙여 지으며, 각 건물의 아랫변은 같은 직선 위에 놓인다. 건설이 끝나면 도시에 공기를 채워야 하므로, 공기가 빠져나가지 않도록 거대한 유리벽으로 도시를 둘러싼다. 이 벽도 건물의 변에 평행한 변을 가진 직사각형이다.

화성에서 공기를 유지하는 데는 비용이 많이 들기 때문에, 가능한 모든 배정 중에서 필요한 공기의 양이 가장 적은 배정 하나를 골라야 한다. 단위 넓이의 정사각형을 채우는 데 공기 1단위가 필요하다.

첫 번째 예시 테스트에서 나올 수 있는 도시로, 공기는 20단위만 필요하다. 너비가 3인 건물은 짓지 않기로 했다.

첫째 줄에 문제 설명의 두 정수 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 1 000 000)

다음 N개의 줄에 i번째 건물의 너비와 높이를 나타내는 두 정수 Wi와 Hi가 주어진다. (1 ≤ Wi, Hi ≤ 1 000 000) 모든 순서쌍 (Wi, Hi)는 서로 다르다.

첫째 줄에 필요한 공기의 최솟값을 출력한다.