在这次开采计划中，计划对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,...,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)

对于前20%的数据，n <= 500, M <= 100

对于前50%的数据，n <= 10000, M <= 100

对于前60%的数据，n <= 10000, M <= 500

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