시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 148 | 96 | 83 | 66.935% |
화학자 정우는 물질 결합 실험을 하고 있다. 정우는 $N$($1 \le N \le 3 \cdot 10^5$)개의 물질을 가지고 있고, 각 물질은 $(a, b)$라는 두 개의 정수로 특성을 표현할 수 있다.
정우가 가진 물질들은 서로 합칠 수 있는데, 특성이 $(a, b)$인 물질과 $(c, d)$인 물질을 결합할 경우 결합에 사용된 물질은 사라지고 $ad + bc$ 만큼의 에너지가 발생하며 특성이 $(a + c, b + d)$인 물질이 새로 생겨나게 된다.
정우는 가지고 있는 $N$개의 물질을 하나의 물질로 합치려고 한다. 정우는 갖고 있는 물질 중 임의의 두 물질을 골라 하나로 합칠 수 있다. 정우가 물질을 합치는 과정에서 얻을 수 있는 에너지의 양의 합의 최대치를 출력하는 프로그램을 작성해보자.
첫 줄에 정우가 가진 물질의 수 $N$($1 \le N \le 3 \cdot 10^5$)이 주어진다.
둘째 줄부터 $N$줄에 걸쳐 정우가 가진 물질의 특성을 나타내는 두 정수 $a_i$, $b_i$($ 0 \le a_i, b_i \le 1000$)가 순서대로 주어진다.
첫째 줄에 정우가 얻을 수 있는 에너지의 양 최대치를 출력한다.
5 3 2 1 1 2 6 0 4 3 5
128
첫 번째 예시에서는 다음과 같은 순서를 거치면 가장 많은 에너지를 얻을 수 있다.
각 과정에서 나온 에너지의 양을 모두 더하면 8 + 40 + 5 + 75 = 128 이고 이 경우가 최대다.