Deus Non Vult

Deus Non Vult

Deus Non Vult

背景

全小将是宇宙国的一名司令官,现在他准备发动一次苦迭打,但是他遭受了来自张泰玩将军的空输进攻。
全小将通过情报人员提前得知了这次空输进攻,张泰玩将军提前召集了\(n\)支空输部队,第\(i\)支空输部队将在\(t_i\)时刻到达并且拥有\(k_i\)的空输兵力,为了击败这只空输部队,全小将至少需要在\(t_i\)时刻拥有\(k_i\)兵力的部队才能抵御这次空输进攻,否则则不能抵御失败。
全小将会在0时刻开始通过发布军令来召集空输部队抵御这次进攻,囿于宇宙国奇怪的军事规则和全小将较低的军衔,他只能发布两种军令:1.在下一时刻增加1兵力的空输部队;2.在下一时刻解散所有的空输部队(即使下一时刻空输兵力为0)(若没有部队,则不执行)。如果他在某一时刻没有发布军令,这一时刻将延续上一时刻的军令。特别地,在0时刻时,全小将空输兵力为0,若没有发布军令,视为发布第二种军令。
然而,每在1单位时刻拥有1单位兵力,全小将就要消耗1宇宙元的经费,虽然这次召集部队非常重要,全小将的经费却有限,并且全小将希望能消耗尽量少的经费来解决这次进攻。
现在,他想知道他能否抵御住这次进攻,如果能,他希望能知道最少需要消耗多少经费,如果不能,他就将被永远地钉在历史的耻辱柱上。
他允诺你事成之后让你当带统勇政务第一首席秘书官并希望你能解决这个问题。

输入

第一行是一个整数代表有t组数据(\(1<=t<=10\))
第一行是两个整数\(n,m\),代表张泰玩派出了几支空输部队和全小将的经费数(\(1<=n<=10^2,1<=m<=10^{18}\))
第二行是\(n\)个整数\(k_1,k_2,k_3,…,k_n\),代表第\(i\)支空输部队到达的时间(\(k_1<k_2<k_3<…<k_n,1<=k_i<=10^9\))
第三行是\(n\)个整数\(h_1,h_2,h_3,…,h_n\),代表第\(i\)支空输部队的兵力(\(1<=h_i<=10^9\))

输出

如果全小将能抵御这次空输进攻,输入一个整数,代表全小将最少需要花费的经费,如果不能,则输出"Deus Non Vult"(不包括引号)

样例

输入

3
2 16
6 14
2 4
2 10
3 5
1 4
4 114514
810 1026 1212 1919
306  516 518 629 

输出

13
10
Deus Non Vult

样例解释

对于第一组数据,分别在[4,10]时刻发布命令1,在[6,14]时刻发布命令2,这样在[6,14]时刻就分别拥有[2,4]的兵力,需要消耗13宇宙元的经费
对于第二组数据,在[1]时刻发布命令1,在[5]时刻发布命令2,这样在[3,5]时刻就分别拥有[2,4]的兵力,需要消耗10宇宙元的经费
对于第三组数据,分别在[504,1290]时刻发布命令1,在[1212,1919]时刻分别发布命令2,这样就在[810,1026,1212,1919]时刻拥有306,522,708,629]兵力的部队,需要消耗449121军费,114514军费不足以召集部队,则"Deus Non Vult"

信息

ID
1317
难度
8
分类
(无)
标签
(无)
递交数
85
已通过
7
通过率
8%
被复制
1
上传者

相关

在下列比赛中:

2022迎新春赛