Preparing NOJ

Photo to Remember

2000ms 262144K


One day n friends met at a party, they hadn't seen each other for a long time and so they decided to make a group photo together.

Simply speaking, the process of taking photos can be described as follows. On the photo, each photographed friend occupies a rectangle of pixels: the i-th of them occupies the rectangle of width wi pixels and height hi pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends, is W × H, where W is the total sum of all widths and H is the maximum height of all the photographed friends.

As is usually the case, the friends made n photos — the j-th (1 ≤ j ≤ n) photo had everybody except for the j-th friend as he was the photographer.

Print the minimum size of each made photo in pixels.


The first line contains integer n (2 ≤ n ≤ 200 000) — the number of friends.

Then n lines follow: the i-th line contains information about the i-th friend. The line contains a pair of integers wi, hi (1 ≤ wi ≤ 10, 1 ≤ hi ≤ 1000) — the width and height in pixels of the corresponding rectangle.


Print n space-separated numbers b1, b2, ..., bn, where bi — the total number of pixels on the minimum photo containing all friends expect for the i-th one.

Sample Input:

1 10
5 5
10 1

Sample Output:

75 110 60 

Sample Input:

2 1
1 2
2 1

Sample Output:

6 4 6 



Provider CodeForces

Origin VK Cup 2015 - Qualification Round 1

Code CF522B


*specialdata structuresdpimplementation

Submitted 18

Passed 13

AC Rate 72.22%

Date 03/03/2019 22:59:46


Nothing Yet