UOJ Logo

NOI.AC

3S 1024MB

#713. 魔术

统计

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$