시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB32116113954.510%

문제

K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 컨테이너의 무게만큼 비용을 발생시킨다.

컨테이너마다 우선순위가 있는데 우선순위는 1 이상 M 이하의 정수로 표현된다. 우선순위가 1에 가까울 수록 높은 우선순위를 가지고, M에 가까울 수록 낮은 우선순위를 가진다. M개의 각 우선순위에 대하여 해당 우선순위를 갖는 컨테이너가 적어도 하나 존재한다.

컨테이너는 레일을 통해 하나씩 오고, 우선순위가 낮은 컨테이너를 먼저 적재한다. 낮은 우선순위의 컨테이너들이 모두 적재되지 않은 상태에서 높은 우선순위의 컨테이너가 온다면 레일의 처음으로 보낸다. 레일의 처음으로 보낼 때, 컨테이너의 무게만큼 비용이 발생한다. 낮은 우선순위의 컨테이너가 온다면, 무조건 적재한다.

컨테이너의 우선순위가 같을 땐, 무게가 무거운 컨테이너를 아래에 위치시킨다.

컨테이너의 우선순위가 같으면서 무게도 같은 경우는 어느 것이 위에 있어도 상관없다.

우선순위는 같으나, 무게가 가벼운 컨테이너가 먼저 적재돼 있을 경우, 가벼운 컨테이너가 무거운 컨테이너 위로 갈 수 있도록 컨테이너를 빼내고 다시 적재한다. 이 과정을, 가벼운 컨테이너가 모두 빠질 때까지 반복한다. 이 과정에서 컨테이너를 뺄 때와 적재될 때 컨테이너의 무게만큼 비용이 발생한다.

작업이 모두 끝난 후 도커 씨가 부담해야 할 비용을 출력하자.

입력

첫째 줄엔 컨테이너의 개수 $N$과 우선순위의 종류 $M$이 주어진다. ($1 \le M \le N \le 100$)

2번째 줄부터 $N + 1$번째 줄까지는 컨테이너들의 우선순위 $P$($1 \le P \le M$), 무게 $W$($1 \le W \le 100$)가 순서대로 주어진다.

레일에 배치되는 순서는 입력으로 주어지는 컨테이너의 순서와 동일하다.

모든 입력은 1 이상의 정수이다.

출력

로봇이 들어올린 무게들의 합을 출력한다.

예제 입력 1

3 1
1 2
1 1
1 3

예제 출력 1

12

예제 입력 2

4 2
1 2
1 1
2 1
2 2

예제 출력 2

11

예제 입력 3

9 3
3 3
3 2
3 1
2 3
2 2
2 1
1 3
1 2
1 1

예제 출력 3

18

예제 입력 4

9 3
3 1
3 2
3 3
2 1
2 2
2 3
1 1
1 2
1 3

예제 출력 4

42

노트

우선순위는 같지만, 무게순으로 배치해야 하는 경우는 예시 1을 기준으로 설명한다.


 

처음 2개의 컨테이너는 무게순대로 넣는 것이 가능하다. 이 과정에서 로봇은 3(1+2)의 무게를 들어올린다.


 

하지만 다음 컨테이너는 적재된 컨테이너 상단부보다 무겁기 때문에 재배치 해야하고 결과는 아래 그림과 같다. 이 과정에서 로봇은 6(1+2+3)의 무게를 들어올린다.


 

재배치 하느라 꺼낸 컨테이너를 다시 넣을 땐, 무게순으로 넣어준다. 이 과정에서 로봇은 3(1+2)의 무게를 들어올리고 총 12의 무게를 들어올리게 된다.


 

우선순위가 맞지 않는 경우에 대해선 예시 2를 기준으로 설명한다.


 

처음 2개의 컨테이너는 현재 우선순위인 1과 맞지 않기 때문에 레일의 처음으로 이동시킨다. 이 과정에서 로봇은 3(1+2)의 무게를 들어올린다.


 

이후 컨테이너 적재는 예시 1과 동일하다.