D - Contest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

あるプログラミングコンテストに N チームが参加しました。
このコンテストの競技時間は T 分間でした。
チーム i の正解問題数は A_i 、最終正解時刻は B_i でした。

このコンテストでは、以下の規則で順位を決定します。

  • より多くの問題を正解した方が上位となる。
  • 正解問題数が同じチーム同士では、その中で最終正解時刻がより小さい方が上位となる。
  • 正解問題数も最終正解時刻も同じチーム同士では、その中でチーム番号がより小さい方が上位となる。

1 位のチームの正解問題数を A' 、最終正解時刻を B' とします。
全てのチームについて、以下の値 G_i を求めてください。

  • G_i = T \times (A' - A_i) + (B_i - B')

制約

  • 入力は全て整数
  • 1 \le N \le 1000
  • 1 \le T \le 1000
  • 1 \le A_i \le 1000
  • 1 \le B_i \le T

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

全体で N 行出力せよ。
そのうち i 行目には、 G_i を整数として出力せよ。

入力例 1

6 120
3 80
4 90
5 120
5 100
3 110
4 70

出力例 1

220
110
20
0
250
90

このコンテストには 6 チームが参加し、競技時間は 120 分でした。
1 位になったのは、 5 問正解して最終正解時刻が 100 であるチーム 4 です。
よって、各 G_i は次の通りです。

  • G_1 = 120 \times (5-3) + (80-100) = 220
  • G_2 = 120 \times (5-4) + (90-100) = 110
  • G_3 = 120 \times (5-5) + (120-100) = 20
  • G_4 = 120 \times (5-5) + (100-100) = 0
  • G_5 = 120 \times (5-3) + (110-100) = 250
  • G_6 = 120 \times (5-4) + (70-100) = 90

Problem Statement

N teams competed in a programming contest.
The contest lasted T minutes.
Team i solved A_i problems, and the last acceptance time was B_i.

In this contest, the ranks are determined as follows:

  • Those who solved more problems rank higher.
  • Among those with the same number of solved problems, those with earlier last acceptance time rank higher.
  • Among those with the same number of solved problems and last acceptance time, those with a smaller team number rank higher.

Let A' be the number of problems solved by the team ranked first, and B' be its last acceptance time.
Find the following value G_i for each team.

  • G_i = T \times (A' - A_i) + (B_i - B')

Constraints

  • All input values are integers.
  • 1 \le N \le 1000
  • 1 \le T \le 1000
  • 1 \le A_i \le 1000
  • 1 \le B_i \le T

Input

The input is given from Standard Input in the following format:

N T
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print N lines.
The i-th line should contain G_i as an integer.

Sample Input 1

6 120
3 80
4 90
5 120
5 100
3 110
4 70

Sample Output 1

220
110
20
0
250
90

Six teams participated in this contest, and it lasted 120 minutes.
The first-ranked team is team 4, which solved five problems and the last acceptance time is 100.
Therefore, G_i is calculated as follows.

  • G_1 = 120 \times (5-3) + (80-100) = 220
  • G_2 = 120 \times (5-4) + (90-100) = 110
  • G_3 = 120 \times (5-5) + (120-100) = 20
  • G_4 = 120 \times (5-5) + (100-100) = 0
  • G_5 = 120 \times (5-3) + (110-100) = 250
  • G_6 = 120 \times (5-4) + (70-100) = 90