\(i\) 番目の参加者が部屋から出るまでにかかる時間は \(S_i \times M + E_i\) と表すことができます。したがって、\(S_i \times M + E_i\) の値の小さい順に並び替えることで部屋から出る順番を求めることができます。

「同じタイミングに部屋を出る時は予選順位が高い方から部屋を出る」という部分を実現する方法はいくつかありますが、例えば

• 安定ソートを行う
• \(S_i \times M + E_i\) の値ではなく \(\text{INF}(S_i \times M + E_i)+i\) の小さい順に並び替える

などで実現することができます。

実装例(Python3)

n, m = map(int, input().split())
a = []
for i in range(n):
    s, e = map(int, input().split())
    a.append((s * m + e, i))
a.sort()
ans = [c[1] + 1 for c in a]
print(*ans)