{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e听说$eom$是一个钓鱼大师,你想承认他为你的导师。众所周知,如果你想成为大师的徒弟,你应该通过考验。所以当你找到钓鱼大师$eom$时,考验如下:\u003cbr\u003e\u003cbr\u003e池塘里有$n$条鱼。对于第$i$ - 第$th$ 条鱼,至少需要$t_i$分钟来炖煮(煮过头是可以接受的)。为了简化这个问题,抓一条鱼的时间是$k$分钟。你可以一次抓一条鱼,因为只有一个锅,一次只能炖一条鱼。当你抓鱼的时候,你不能把已经抓到的生鱼放进锅里,这意味着如果你开始抓鱼,你不能在$k$分钟后停下来;当你不在抓鱼时,你可以把已经炖好的鱼(炖了不少于$t_i$分钟)从锅里拿出来,或者把生鱼放进锅里,这两个操作不需要时间。注意,如果锅里的鱼没有炖够时间,你不能把它拿出来,但你可以去抓另一条鱼,或者什么都不做等一会儿,直到它炖够。\u003cbr\u003e\u003cbr\u003e现在$eom$希望你尽快抓鱼并炖煮所有的鱼(你肯定知道只有足够炖煮的鱼才能吃),这样他就可以吃上满意的一餐。如果你能在最短的时间内完成,$eom$会接受你为他的徒弟,并说“我吃饱了!”。如果不能,$eom$不会接受你,并说“你完了!你是傻瓜!”\u003cbr\u003e\u003cbr\u003e如果你安排时间得当,通过考验的最短时间是多少?\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个整数$T(1 \\leq T \\leq 20)$,表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,第一行包含两个整数$n(1 \\leq n \\leq 10^5), k(1 \\leq k \\leq 10^9)$,表示池塘里的鱼的数量和抓一条鱼所需的时间。\u003cbr\u003e\u003cbr\u003e第二行包含$n$个整数,$t_1, t_2, \\dots , t_n(1 \\leq t_i \\leq 10^9)$,表示炖煮第$i$ - 第$th$ 条鱼所需的最少时间。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,每行输出一个整数,表示通过考验的最短时间。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 5\r\n5 5 8\r\n2 4\r\n3 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e23\r\n11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e案例1:抓第3条鱼(5分钟),放进第3条鱼,抓第1条鱼(5分钟),等待(3分钟),\u003cbr\u003e\u003cbr\u003e拿出第3条鱼,放进第1条鱼,抓第2条鱼(5分钟),\u003cbr\u003e\u003cbr\u003e拿出第1条鱼,放进第2条鱼,等待(5分钟),拿出第2条鱼。\u003cbr\u003e\u003cbr\u003e案例2:抓第1条鱼(4分钟),放进第1条鱼,抓第2条鱼(4分钟),\u003cbr\u003e\u003cbr\u003e拿出第1条鱼,放进第2条鱼,等待(3分钟),拿出第2条鱼。\u003cbr\u003e"}}]}