24533번 - 결합

문제

화학자 정우는 물질 결합 실험을 하고 있다. 정우는 $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$)가 순서대로 주어진다.

출력

첫째 줄에 정우가 얻을 수 있는 에너지의 양 최대치를 출력한다.

제한

힌트