조각상
면접 대비시간 제한1초메모리 제한512 MB
서로 다른 가로등에 놓인 K개의 조각상이 주어질 때, 위치가 커질수록 크기가 커지도록 서로 다른 가로등에 다시 배치하면서 크기와 이동 거리의 곱의 합을 최소화한다.
문제
매일 원격 근무를 하며 느끼는 외로움에서 벗어나려고, Erika는 조각을 새로운 취미로 삼았다. 그녀는 이미 많은 조각상을 모아 두었고, 시 당국은 그녀가 야외에 작품을 전시하는 것을 허락했다.
Erika는 조각상이 잘 보이길 바라므로, 각 조각상은 서로 다른 가로등 아래에 놓여야 한다. 또한 배치가 아름다워야 하는데, 이는 조각상을 크기 순으로 늘어놓아 가장 작은 조각상은 거리 앞쪽에, 가장 큰 조각상은 거리 뒤쪽에 놓는다는 뜻이다.
Erika는 조각상을 배치했지만 크기 순으로 놓는 것을 잊었고, 이제 두 가지 조건에 맞게 조각상을 다시 배치해야 한다.
거리에는 N개의 가로등이 같은 간격으로 놓여 있으며, 거리 앞쪽부터 1번, 뒤쪽 끝이 N번이다. 크기 s인 조각상을 i번 가로등에서 j번 가로등으로 옮기는 데 걸리는 시간은 s × |i − j| 단위 시간이라고 추정한다. Erika가 가능한 가장 빠른 방법을 쓴다고 할 때, 모든 조각상을 다시 배치하는 데 걸리는 시간은 얼마인가? 조각상이 없는 가로등 아래에 조각상을 놓아도 된다.
입력
첫째 줄에 가로등의 수 N과 조각상의 수 K가 공백으로 구분되어 주어진다. 다음 K개의 줄에는 각각 두 정수가 공백으로 구분되어 주어지며, i + 1번째 줄에는 i번째 조각상을 나타내는 Pi와 Si가 주어진다. Pi는 조각상이 놓여 있는 가로등의 번호이고, Si는 조각상의 크기이다.
출력
각 조각상이 서로 다른 가로등 아래에 있고, 가로등 번호가 커질수록 조각상의 크기도 커지도록 조각상을 옮기는 데 필요한 최소 시간을 한 줄에 하나의 정수로 출력한다.
제한
- 1 ≤ K ≤ N ≤ 5 000
- 모든 1 ≤ i ≤ K에 대해 1 ≤ Si ≤ 1 000 000, 1 ≤ Pi ≤ N