문제 설명
대형 쇼핑몰에서 쇼핑을 마친 \(N\)명의 고객들이 계산을 하고 쇼핑몰을 떠나고자 계산대 앞에 줄을 서 있다. 각 고객은 커다란 짐수레(cart)에 물건을 담아 계산대로 간다. 쇼핑몰에는 아래 그림과 같이 \(k\)개의 계산대가 병렬로 배치되어 있다. 쇼핑몰 안내원들은 계산대에 온 사람들을 가장 빨리 계산을 마칠 수 있는 계산대로 안내를 한다. 안내원은 각 계산대에서 기다리고 있는 사람들이 계산을 하는데 얼마나 걸리는지 이미 알고 있다.
안내원이 고객을 계산대로 안내할 때 두 계산대에서 기다려야 할 시간이 같을 경우에는 가장 번호가 작은 계산대로 안내를 한다. 즉 \(3\)번, \(5\)번 계산대에서 기다릴 시간이 똑같이 \(15\)분으로 최소일 경우에는 \(3\)번으로 안내를 한다.
계산을 마친 고객은 출구를 통하여 쇼핑몰을 완전히 빠져 나간다. 만일 계산대에서 계산을 마친 고객의 시간이 동일하다면 출구에 가까운 높은 번호 계산대의 고객부터 먼저 빠져나간다. 예를 들어 두 계산대 \(4\)번과 \(10\)번에서 두 고객이 동시에 계산을 마쳤다면 계산대의 번호가 더 높은 \(10\)번 계산대의 고객이 먼저 쇼핑몰을 나간다. 물건을 계산하는 데이는 종류에 관계없이 동일하게 \(1\)분이 소요된다. 즉, 물건이 \(w\)개 있는 손님이 계산을 마치는 데에는 정확히 \(w\)분이 소요된다.
여러분은 계산대로 들어가기 위해 줄을 서 있는 고객 \(N\)명의 정보(회원번호, 구매한 물건의 수)를 알고 있을때, 이들이 계산을 하고 쇼핑몰을 빠져나오는 순서를 구해야 한다. 계산대로 들어가고 계산대에서 나오는데 걸리는 시간은 없다고 가정한다.
채점 기준
제출된 프로그램은 여러 개의 테스트 케이스로 평가되며, 맞은 테스트 케이스에 대해서 해당 테스트 케이스에 배정된 점수를 받는다. 모든 테스트 케이스를 맞았을 시 100점을 받는다.
각 테스트 케이스에 대한 배점 정보와 제약 조건은 다음과 같다.
1. (20점) 모든 사람이 구입한 물건의 수가 항상 1개이다.\((w_i =1 )\)
2. (36점) 각각 \(1 \le N, k \le 1,000\)
3. (44점) 제약 조건 없음.
안내원이 고객을 계산대로 안내할 때 두 계산대에서 기다려야 할 시간이 같을 경우에는 가장 번호가 작은 계산대로 안내를 한다. 즉 \(3\)번, \(5\)번 계산대에서 기다릴 시간이 똑같이 \(15\)분으로 최소일 경우에는 \(3\)번으로 안내를 한다.
계산을 마친 고객은 출구를 통하여 쇼핑몰을 완전히 빠져 나간다. 만일 계산대에서 계산을 마친 고객의 시간이 동일하다면 출구에 가까운 높은 번호 계산대의 고객부터 먼저 빠져나간다. 예를 들어 두 계산대 \(4\)번과 \(10\)번에서 두 고객이 동시에 계산을 마쳤다면 계산대의 번호가 더 높은 \(10\)번 계산대의 고객이 먼저 쇼핑몰을 나간다. 물건을 계산하는 데이는 종류에 관계없이 동일하게 \(1\)분이 소요된다. 즉, 물건이 \(w\)개 있는 손님이 계산을 마치는 데에는 정확히 \(w\)분이 소요된다.
여러분은 계산대로 들어가기 위해 줄을 서 있는 고객 \(N\)명의 정보(회원번호, 구매한 물건의 수)를 알고 있을때, 이들이 계산을 하고 쇼핑몰을 빠져나오는 순서를 구해야 한다. 계산대로 들어가고 계산대에서 나오는데 걸리는 시간은 없다고 가정한다.
채점 기준
제출된 프로그램은 여러 개의 테스트 케이스로 평가되며, 맞은 테스트 케이스에 대해서 해당 테스트 케이스에 배정된 점수를 받는다. 모든 테스트 케이스를 맞았을 시 100점을 받는다.
각 테스트 케이스에 대한 배점 정보와 제약 조건은 다음과 같다.
1. (20점) 모든 사람이 구입한 물건의 수가 항상 1개이다.\((w_i =1 )\)
2. (36점) 각각 \(1 \le N, k \le 1,000\)
3. (44점) 제약 조건 없음.
입력 설명
입력의 첫 줄에는 \(2\)개의 정수 \(N(1 \le N \le 100,000)\)과 \(k(1 \le k \le 100,000)\)가 주어진다.
다음 줄부터 \(N\)개의 줄에 걸쳐 고객 \(N\)명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다.
\(i\)번째 줄은 줄의 앞에서\(i\)번째 고객의 회원번호 \(id_i(1 \le id_i \le 1,000,000)\)와 그가 구입한 물건의 수 \(w_i(1 \le w_i \le 20)\)로 이루어져 있다. \(N\)명의 회원번호는 모두 다르다.
다음 줄부터 \(N\)개의 줄에 걸쳐 고객 \(N\)명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다.
\(i\)번째 줄은 줄의 앞에서\(i\)번째 고객의 회원번호 \(id_i(1 \le id_i \le 1,000,000)\)와 그가 구입한 물건의 수 \(w_i(1 \le w_i \le 20)\)로 이루어져 있다. \(N\)명의 회원번호는 모두 다르다.
출력 설명
고객 \(N\)명의 회원번호를 쇼핑몰을 빠져나가는 순서대로 \(r_1, r_2, ... r_N\)이라 할 때,
\(1 \times r_1 + 2 \times r_2 + ... + N \times r_N\)의 값을 출력한다. 출력값이 int범위를 넘어갈 수 있음에 유의하라.
\(1 \times r_1 + 2 \times r_2 + ... + N \times r_N\)의 값을 출력한다. 출력값이 int범위를 넘어갈 수 있음에 유의하라.
입력 예시 Copy
10 3
123 4
21 5
34 14
56 1
45 7
723 5
55 7
13 5
910 10
73 3
출력 예시 Copy
13900