{"trustable":true,"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":"\u003cp\u003eSasha reaches the work by car. It takes exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th song Sasha gets a pleasure which equals \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th song lasts for \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e minutes. \u003c/p\u003e\u003cp\u003eBefore the beginning of his way Sasha turns on some song \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and then he listens to the songs one by one: at first, the song \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, then the song \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e + 1)\u003c/span\u003e, then the song number \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e + 2)\u003c/span\u003e, and so on. He listens to songs until he reaches the work or until he listens to the last song in his playlist. \u003c/p\u003e\u003cp\u003eSasha can listen to each song to the end or \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second case he listens to the song for integer number of minutes, at least half of the song\u0027s length. Formally, if the length of the song equals \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003c/span\u003e minutes, Sasha listens to it for no less than \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/c1101b2a81d5d35020f2facfed1f8cbc?v\u003d1715792513\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e minutes, then he immediately switches it to the next song (if there is such). For example, if the length of the song which Sasha wants to \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e listen to, equals \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e minutes, then he should listen to it for at least \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e minutes, if the length of the song equals \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e minutes, then he should listen to it for at least \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e minutes.\u003c/p\u003e\u003cp\u003eIt takes no time to switch a song.\u003c/p\u003e\u003cp\u003eSasha wants to listen \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e no more than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e songs. If the last listened song plays for less than half of its length, then Sasha doesn\u0027t get pleasure from it and that song is not included to the list of \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e listened songs. It is not allowed to skip songs. A pleasure from a song does not depend on the listening mode, for the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th song this value equals \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eHelp Sasha to choose such \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and no more than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e songs for \u003cspan class\u003d\"tex-font-style-it\"\u003epartial\u003c/span\u003e listening to get the maximum pleasure. Write a program to find the maximum pleasure Sasha can get from the listening to the songs on his way to the work.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of songs in the playlist, the number of songs Sasha can listen to \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e and time in minutes which Sasha needs to reach work. \u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e equals the pleasure Sasha gets after listening to the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th song.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e positive integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e equals the length of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th song in minutes.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint the maximum pleasure Sasha can get after listening to the songs on the way to work. \u003c/p\u003e"}},{"title":"Examples","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\u003e7 2 11\n3 4 3 5 1 4 6\n7 7 3 6 5 3 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e8 4 20\n5 6 4 3 7 5 4 1\n10 12 5 12 14 8 5 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e19\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e1 1 5\n6\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e1 1 3\n4\n7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example Sasha needs to start listening from the song number \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. He should listen to it \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e (for \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e minutes), then listen to the song number \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e to the end (for \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e minutes) and then \u003cspan class\u003d\"tex-font-style-it\"\u003epartly\u003c/span\u003e listen to the song number \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e (for \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e minutes). After listening to these songs Sasha will get pleasure which equals \u003cspan class\u003d\"tex-span\"\u003e4 + 3 + 5 \u003d 12\u003c/span\u003e. Sasha will not have time to listen to the song number \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e because he will spend \u003cspan class\u003d\"tex-span\"\u003e4 + 3 + 3 \u003d 10\u003c/span\u003e minutes listening to songs number \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and only \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e minute is left after that. \u003c/p\u003e"}}]}