{"trustable":false,"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Now there is a game called the new man down 100th floor. The rules of this game is: \n \u003cbr\u003e \n \u003cstrong\u003e1.\u003c/strong\u003e\u0026nbsp;\u0026nbsp;At first you are at the 1st floor. And the floor moves up. Of course you can choose which part you will stay in the first time. \n \u003cbr\u003e \n \u003cstrong\u003e2.\u003c/strong\u003e\u0026nbsp;\u0026nbsp;Every floor is divided into M parts. You can only walk in a direction (left or right). And you can jump to the next floor in any part, however if you are now in part “y”, you can only jump to part “y” in the next floor! (1\u0026lt;\u003dy\u0026lt;\u003dM) \n \u003cbr\u003e \n \u003cstrong\u003e3.\u003c/strong\u003e\u0026nbsp;\u0026nbsp;There are jags on the ceils, so you can only move at most T parts each floor. \n \u003cbr\u003e \n \u003cstrong\u003e4.\u003c/strong\u003e\u0026nbsp;\u0026nbsp;Each part has a score. And the score is the sum of the parts’ score sum you passed by. \n \u003cbr\u003eNow we want to know after you get the 100th floor, what’s the highest score you can get. \n\u003c/div\u003e\n游戏共有N层,每层有M格,你目前在第一层的X位置。第一层在最上面。可以往下跳。\u003c/br\u003e\n如果在第i层的y位置,向下跳就是i+1层的y位置。每一层最多移动T步,每一层都有一些分数。\u003c/br\u003e求如何移动,分数最多。\n"}},{"title":"Input","value":{"format":"HTML","content":"The first line of each case has four integer N, M, X, T(1\u0026lt;\u003dN\u0026lt;\u003d100, 1\u0026lt;\u003dM\u0026lt;\u003d10000, 1\u0026lt;\u003dX, T\u0026lt;\u003dM). N indicates the number of layers; M indicates the number of parts. At first you are in the X-th part. You can move at most \n\u003cstrong\u003eT parts\u003c/strong\u003e in every floor in only one direction. \n\u003cbr\u003eFollowed N lines, each line has M integers indicating the score. (-500\u0026lt;\u003dscore\u0026lt;\u003d500)\n有多组测试数据\u003c/br\u003e\n第一行4个整数N,M,X,T (1\u0026lt;\u003dN\u0026lt;\u003d100, 1\u0026lt;\u003dM\u0026lt;\u003d10000, 1\u0026lt;\u003dX, T\u0026lt;\u003dM)\u003c/br\u003e\n接下来N行,每行M个数,表示每个格子的分数。(-500\u0026lt;\u003dscore\u0026lt;\u003d500)"}},{"title":"Output","value":{"format":"HTML","content":"输出能得到的最高分。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3 3 2 1\n7 8 1 \n4 5 6 \n1 2 3 \u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e29\u003c/pre\u003e"}}]}