{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/mandarin/WEASELSC.pdf\"\u003emandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/russian/WEASELSC.pdf\"\u003erussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/SEPT17/vietnamese/WEASELSC.pdf\"\u003evietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\u003cp\u003eWeasel loves histograms. Weasel feels that he is very much out of shape and asks for Chef’s advice. Chef convinced Weasel that the only way to get back in shape is to work out. Weasel decides to follow Chef’s advice and has formulated the greatest workout plan - to reflect his love for histograms - in which he will go down the staircase every day. However, Weasel is not in the best shape, so, for starters, he can only go down at most \u003cb\u003eK\u003c/b\u003e steps.\u003c/p\u003e\r\n\r\n\u003cp\u003eFormally, a staircase is a set of adjacent rectangles with at most \u003cb\u003eK\u003c/b\u003e changes of height. These rectangles should have either increasing or decreasing heights. The rectangles should start from the bottom (see images in the explanation section for clarification), and the height of rectangle at \u003cb\u003ei\u003c/b\u003e-th position shouldn\u0027t be more than \u003cb\u003ehistogram\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. \u003c/p\u003e\r\n\r\n\u003cp\u003eFor each of the \u003cb\u003eT\u003c/b\u003e cases, you have to find the greatest area of a staircase that matches the above-mentioned restrictions.\u003cp\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp\u003eFor each of the \u003cb\u003eT\u003c/b\u003e cases, you will be given two integers \u003cb\u003eN\u003c/b\u003e, denoting the number of elements of the histogram, and \u003cb\u003eK\u003c/b\u003e, the maximum number of steps, on the first line.\u003c/p\u003e\r\n\u003cp\u003eFor each of the \u003cb\u003eT\u003c/b\u003e cases, you will be given \u003cb\u003ehistogram\u003c/b\u003e array on the second line. \u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case you should print an integer, the maximum area of a staircase that satisfies Weasel\u0027s conditions.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e5\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003e50\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eThe sum of \u003cb\u003eN\u003c/b\u003e over all testcases does not exceed \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003ehistogram\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask #1\u003c/b\u003e (10 points): \u003cb\u003eK \u003d 0\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask #2\u003c/b\u003e (30 points): The sum of \u003cb\u003eN\u003c/b\u003e over all testcases does not exceed \u003cb\u003e1,500\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask #3\u003c/b\u003e (60 points): original constraints\u003c/li\u003e\r\n\u003c/ul\u003e"}},{"title":"Sample 1","value":{"format":"MD","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\u003e4\r\n5 2\r\n1 2 3 4 5\r\n5 3\r\n9 8 7 6 4\r\n5 1\r\n8 7 5 7 8\r\n4 10\r\n0 1 1 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\r\n33\r\n29\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\r\nThe cells which form the staircase are colored with yellow. The discarded cells are colored with grey.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\u003ch4\u003eCase \u003cb\u003e1\u003c/b\u003e:\u003c/h4\u003e\r\n\u003cp\u003eThe computed area is \u003cb\u003e1\u003c/b\u003e + \u003cb\u003e2\u003c/b\u003e × \u003cb\u003e2\u003c/b\u003e + \u003cb\u003e4\u003c/b\u003e × \u003cb\u003e2\u003c/b\u003e \u003d \u003cb\u003e13\u003c/b\u003e. \u003cbr\u003e There are \u003cb\u003e2\u003c/b\u003e changes of height: we start with a height of \u003cb\u003e1\u003c/b\u003e, we change to \u003cb\u003e2\u003c/b\u003e and then we change to \u003cb\u003e4\u003c/b\u003e.\u003c/p\u003e\r\n\u003cimg height\u003d\"150\" width\u003d\"500\" src\u003d\"CDN_BASE_URL/36a1a32ae18ec60302f4c4b207891026?v\u003d1715838899\"\u003e\r\n\u003ch4\u003eCase \u003cb\u003e2\u003c/b\u003e:\u003c/h4\u003e\r\n\u003cp\u003eThe computed area is \u003cb\u003e9\u003c/b\u003e + \u003cb\u003e7\u003c/b\u003e × \u003cb\u003e2\u003c/b\u003e + \u003cb\u003e6\u003c/b\u003e + \u003cb\u003e4\u003c/b\u003e \u003d \u003cb\u003e33\u003c/b\u003e.\u003c/p\u003e \r\n\u003cimg height\u003d\"150\" width\u003d\"500\" src\u003d\"CDN_BASE_URL/4c6738b253c3120fba346a074e88ab52?v\u003d1715838899\"\u003e\r\n\u003ch4\u003eCase \u003cb\u003e3\u003c/b\u003e:\u003c/h4\u003e\r\n\u003cp\u003eThe computed area is \u003cb\u003e7\u003c/b\u003e × \u003cb\u003e2\u003c/b\u003e + \u003cb\u003e5\u003c/b\u003e × \u003cb\u003e3\u003c/b\u003e \u003d \u003cb\u003e29\u003c/b\u003e.\u003c/p\u003e \r\n\u003cimg height\u003d\"150\" width\u003d\"500\" src\u003d\"CDN_BASE_URL/a830ba80923dc568043b0ec63cb859f4?v\u003d1715838899\"\u003e\r\n\u003cp\u003eHere is another possible solution:\u003c/p\u003e\r\n\u003cimg height\u003d\"150\" width\u003d\"500\" src\u003d\"CDN_BASE_URL/829a7770d92e47f65f69675b9d84785d?v\u003d1715838899\"\u003e\r\n\u003ch4\u003eCase \u003cb\u003e4\u003c/b\u003e:\u003c/h4\u003e\r\n\u003cp\u003eWe take the second and the third cell. We have \u003cb\u003e0\u003c/b\u003e changes in height. This is a viable solution because we can also have staircases with less than \u003cb\u003eK\u003c/b\u003e\r\n changes.\u003c/p\u003e\r\n\u003c/p\u003e"}}]}