{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cpre\u003e\n在圣芙蕾雅学园,琪亚娜.卡斯兰娜和雷电芽衣过着幸福♀快乐的日子。\n但是突然有一天,不知道从哪里突然冒出来一个叫做凯文.卡斯兰娜的人,满嘴说着“老祖宗”,“MEI”等一堆听不懂的话,就把芽衣前辈带走了。\n琪亚娜拿起了从笨蛋老爸那里继承的天火圣裁,走上了拯救芽衣前辈的道路。\n\n想要拯救芽衣前辈,路上需要依次击败n个崩坏兽,击败每个崩坏兽都要损失掉琪亚娜一定的血量,琪亚娜的初始血量上限为k。如果琪亚娜在前进的道路中碰到某只崩坏兽无法击败,那么她拯救芽衣学姐就失败了(如果打败某只崩坏兽后琪亚娜的血量为负数那么琪亚娜会死亡,如果血量为0琪亚娜还可以使用她对芽衣学姐的执着坚强得活下来)。不过琪亚娜身上带着m-1瓶芽衣学姐特制的神秘药水,每瓶药水都可以回复满琪亚娜的血量,也就是说琪亚娜在前进的道路中最多有m次满生命值的状态。\n\n即使琪亚娜用尽了所有的药水还是没能拯救芽衣前辈,琪亚娜还可以使用她对芽衣前辈的爱改变世界线。第一次改变世界线后,琪亚娜可以跳过第一只崩坏兽,然后再次踏上拯救芽衣前辈的旅途。如果再次失败,琪亚娜会第二次改变世界线,跳过第一只和第二只崩坏兽,继续拯救芽衣前辈。也就是说第x次改变世界线,琪亚娜会跳过前x只崩坏兽并回复满所有的神秘药水重新踏上拯救芽衣前辈的道路,直到她成功拯救芽衣前辈。\n\n现在已知这n只崩坏兽会对琪亚娜造成的生命值伤害数值,但是琪亚娜的数学实在是太差了,数学成绩一直是稳定的0分被芽衣前辈教训了好久,现在她跑来问你,在她成功拯救芽衣前辈的那次世界线中,她击败了几只崩坏兽。\n\u003cpre\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cpre\u003e\n第一行包含了三个整数n,m,k(1 \u003c \u003d n,m\u003c \u003d2e5,1\u003c \u003d k \u003c \u003d 1e9),分别代表崩坏兽的个数,琪亚娜在每次世界线中可以拥有的满血量状态次数,以及琪亚娜的血量上限。\n第二行包含了n个整数,依次为这n个崩坏兽会对琪亚娜造成的伤害。(这n个整数的范围为1到k)\n\u003cpre\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cpre\u003e\n在一行中输出琪亚娜成功拯救芽衣前辈的世界线中,击败的崩坏兽个数。\n\u003cpre\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e5 2 5\u003cbr\u003e5 2 1 3 2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e5 1 2\u003cbr\u003e4 2 3 4 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e5 3 3\u003cbr\u003e1 2 3 1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cpre\u003e\n对于第一组样例\n琪亚娜拥有1瓶神秘药水\n在初始的世界线中击败第1只崩坏兽后血量为0,喝下神秘药水后恢复血量为5,继续击败第2,3,4只崩坏兽后血量变为-1,拯救失败。\n第一次跳动世界线后琪亚娜跳过了第一只崩坏兽,在打败第2,3只崩坏兽后剩下2点血量,喝下神秘药水后恢复血量为5,继续击败第4,5只崩坏兽血量为0,成功击败所有崩坏兽拯救芽衣学姐。\n因此答案为4,击败了4只崩坏兽。\n\n对于第二组样例\n琪亚娜没有任何的神秘药水\n在初始的世界线,第1,2,3次跳跃的世界线中琪亚娜均拯救失败。\n只有在第4次跳跃世界先后,琪亚娜直接击败第五只崩坏兽剩下1点血量成功拯救芽衣学姐。\n答案为1,击败了1只崩坏兽。\n\n对于第三组样例\n琪亚娜拥有两瓶神秘药水\n在初始的世界线中,琪亚娜先击败第1,2只崩坏兽,血量变为0,喝下第一瓶神秘药水血量变为3,再击败第3只崩坏兽,血量变为0,喝下第二瓶神秘药水血量变为3,继续击败第4,5只崩坏兽,血量变为1,成功拯救芽衣学姐。\n答案为击败了5只崩坏兽\n\u003cpre\u003e"}}]}