C. 魔术

背景

时钟塔地下的灵墓有丰富的资源

题目描述

在这次开采计划中，计划对$n$种资源（编号为$1$到$n$）进行采集，每种一份。第$i$种资源有魔力量$a_i$，价格$c_i$。

你的魔力上限是$M$，需要从资源中选择一些购买，使它们的魔力量之和模$M$恰好为$t$。在此基础上，希望购买资源所花的代价（价格之和）最少。注意，什么都不选也是一种合法的方案，因此$t=0$时答案为$0$

然而，由于地下开采的危险性，计划开采的资源可能采集失败。同时，目标$t$也可能发生变化。定义$F(i,t)$表示第$i$种资源采集失败（不能购买）时，达到目标$t$的最小代价。如果不能达到，则$F(i,t)=-1$。

你需要对每一个$i \in \{ 1,2,\dots,n \}$，求出$\sum_{t=0}^{M-1} F(i,t)$

输入格式

第一行包含$2$个整数$n,M$，用空格隔开

之后$n$行每行包含两个整数，依次表示每种资源的魔力量$a_i$和价格$c_i$

输出格式

包含$n$行，每行一个整数，第$i$行输出$\sum_{t=0}^{M-1} F(i,t)$

样例输入

5 10
4 3
5 2
3 6
7 10
7 5

样例输出

58
36
78
54
72

数据限制

对于前20%的数据，$n \leq 500, M \leq 100$

对于前50%的数据，$n \leq 10000, M \leq 100$

对于前60%的数据，$n \leq 10000, M \leq 500$

对于100%的数据，$1 \leq n \leq 20000, 1 \leq M \leq 2000, 0 \leq a_i < M, 0 \leq c_i \leq 20000$