{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEvery day, farmer Ion (this is a Romanian name) takes out all his horses, so they may run and play. When they are done, farmer Ion has to take all the horses back to the stables. In order to do this, he places them in a straight line and they follow him to the stables. Because they are very tired, farmer Ion decides that he doesn\u0027t want to make the horses move more than they should. So he develops this algorithm: he places the 1st P\u003csub\u003e1\u003c/sub\u003e horses in the first stable, the next P\u003csub\u003e2\u003c/sub\u003e in the 2nd\r\nstable and so on. Moreover, he doesn\u0027t want any of the \u003cb\u003eK\u003c/b\u003e stables he owns to be empty, and no horse must be left outside. Now you should know that farmer Ion only has black or white horses, which don\u0027t really get along too well. If there are \u003cb\u003ei \u003c/b\u003eblack horses and \u003cb\u003ej\u003c/b\u003e white horses in one stable, then the coefficient of unhappiness of that stable is\u003cb\u003e i*j\u003c/b\u003e. The total coefficient of unhappiness is the\r\nsum of the coefficients of unhappiness of every of the K stables.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eDetermine a way to place the \u003cb\u003eN\u003c/b\u003e horses into the \u003cb\u003eK\u003c/b\u003e stables, so that the total coefficient of unhappiness is minimized.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOn the 1st line there are 2 numbers: \u003cb\u003eN\u003c/b\u003e (1 ≤ N ≤ 500) and \u003cb\u003eK\u003c/b\u003e (1 ≤ K ≤ N). On the next N lines there are N numbers. The i-th of these lines contains the color of the i-th horse in the sequence: 1 means that the horse is black, 0 means that the horse is white.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYou should only output a single number, which is the minimum possible value for the total coefficient of unhappiness.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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\u003e6 3\r\n1\r\n1\r\n0\r\n1\r\n0\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ePlace the first 2 horses in the first stable, the next 3 horses in the 2nd stable and the last horse in the 3rd stable.\r\n\u003c/div\u003e\u003c/div\u003e"}}]}