{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/DEC13/mandarin/REIGN.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/DEC13/russian/REIGN.pdf\" rel\u003d\"nofollow noreferrer noopener\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\n\u003cp\u003eThe Baratheons have been ruling in the Seven Kingdoms for many years. They have seen a lot: prosperity and hunger, tranquility and rebellions, live and death. But nevertheless, they still hold the throne.\u003c/p\u003e\n\n\u003cp\u003eKing Joffrey Baratheon\u0027s reign is running now. As a wise man, he honors the history of his family. So, he commanded to build up \u003cb\u003etwo\u003c/b\u003e monuments, that will remind about some historical periods of the Baratheons.\u003c/p\u003e\n\n\u003cp\u003eFormally, the Baratheons have been ruling for \u003cb\u003eN\u003c/b\u003e years. Every year is described by an integer \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, the level of prosperity in \u003cb\u003ei\u003c/b\u003e-th year. If \u003cb\u003ei\u003c/b\u003e-th year was a great year, then \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e might be a positive integer. Otherwise, if \u003cb\u003ei\u003c/b\u003e-th year was a horrible year, then \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e might be a negative integer.\u003c/p\u003e\n\n\u003cp\u003eEach historical period can be described as two integers \u003cb\u003eS\u003c/b\u003e and \u003cb\u003eF\u003c/b\u003e, the start and the finish of the period respectively. Of course, \u003cb\u003eS\u003c/b\u003e is not greater than \u003cb\u003eF\u003c/b\u003e for each period, that we consider in this task.\u003c/p\u003e\n\n\u003cp\u003eYou are to pick two historical periods, but there are some rules:\u003c/p\u003e\n\n\u003cul\u003e\u003cli\u003eTwo periods shouldn\u0027t have common years. I.e. a period [1, 5] has no common years with a period [6, 7];\u003c/li\u003e\n\u003cli\u003eThe first period should start earlier than the second one. I.e. a period [1, 5] starts earlier than [6, 7];\u003c/li\u003e\n\u003cli\u003eTwo periods shouldn\u0027t be too close to each other. There must be at least \u003cb\u003eK\u003c/b\u003e years between the finish of the first period and the start of the second period. I.e. periods [1, 5] and [10, 10] can be chosen in case \u003cb\u003eK\u003c/b\u003e equals to 4, while they can\u0027t in case \u003cb\u003eK\u003c/b\u003e equals to 5.\u003c/li\u003e\n\u003cli\u003eThe sum of the levels of prosperity in chosen years should be as big as possible.\u003c/li\u003e\n\u003c/ul\u003e\n\nAfterwards, you should report the sum of the levels of prosperity in chosen years to your King. Make everything right, otherwise King Joffrey won\u0027t be merciful!\n\n\u003ch3\u003eInput\u003c/h3\u003e\nThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003cbr /\u003e\nThe first line of each test case contains two integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eK\u003c/b\u003e denoting the length of the Baratheons\u0027 reign and the minimal amount of years between two chosen periods.\u003cbr /\u003e\nThe second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e denoting the levels of prosperity in corresponding years.\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\nFor each test case, output a single line containing the required integer.\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 5;\u003c/li\u003e\n\u003cli\u003e2 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e;\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eK\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e;\u003c/li\u003e\n\u003cli\u003e-10\u003csup\u003e9\u003c/sup\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e for every 1 ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e;\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eK\u003c/b\u003e + 2 ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\u003cp\u003e \u003c/p\u003e\n"}},{"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\u003e3\n5 3\n-1 1 2 3 -1\n8 3\n5 5 -1 -2 3 -1 2 -2\n6 0\n5 -1 5 0 -1 9\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-2\n12\n18\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003eThere are \u003cb\u003eT\u003c/b\u003e \u003d 3 test cases the input.\u003c/p\u003e\n\u003cp\u003eThe first test case: \u003cb\u003eN\u003c/b\u003e equals to 5, \u003cb\u003eK\u003c/b\u003e equals to 3, A[] equals to {-1, 1, 2, 3, -1}. There is the only option: we have to choose [1, 1] and [5, 5] periods.\u003c/p\u003e\n\u003cp\u003eThe second test case: \u003cb\u003eN\u003c/b\u003e equals to 8, \u003cb\u003eK\u003c/b\u003e equals to 3, A[] equals to {5, 5, -1, -2, 3, -1, 2, -2}. It is optimal to choose [1, 2] and [7, 7] periods. That is the only optimal choice that you can make.\u003c/p\u003e\n\u003cp\u003eThe second test case: \u003cb\u003eN\u003c/b\u003e equals to 6, \u003cb\u003eK\u003c/b\u003e equals to 0, A[] equals to {5, -1, 5, 0, -1, 9}. It is optimal to choose [1, 3] and [6, 6] periods. But that is not the only optimal choice that you can make.\u003c/p\u003e"}}]}