{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003clink href\u003d\"css/light_oj.css\" rel\u003d\"stylesheet\" type\u003d\"text/css\" /\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tThe people of \u003cspan data-scayt_word\u003d\"Mohammadpur\" data-scaytid\u003d\"1\"\u003eMohammadpur\u003c/span\u003e have decided to paint each of their houses red, green, or blue. They\u0026#39;ve also decided that no two neighboring houses will be painted the same color. The neighbors of house \u003cb\u003ei\u003c/b\u003e are houses \u003cb\u003ei-1\u003c/b\u003e and \u003cb\u003ei+1\u003c/b\u003e. The first and last houses are not neighbors.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tYou will be given the information of houses. Each house will contain three integers \u003cb\u003e\u0026quot;R G B\u0026quot;\u003c/b\u003e (quotes for clarity only), where \u003cb\u003eR, G \u003c/b\u003eand\u003cb\u003e B\u003c/b\u003e are the costs of painting the corresponding house red, green, and blue, respectively. Return the minimal total cost required to perform the work.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e\u0026le; 100)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tEach case begins with a blank line and an integer \u003cb\u003en (1 \u0026le; n \u0026le; 20)\u003c/b\u003e denoting the number of houses. Each of the next \u003cb\u003en\u003c/b\u003e lines will contain 3 integers \u003cb\u003e\u0026quot;R G B\u0026quot;\u003c/b\u003e. These integers will lie in the range \u003cb\u003e[1, 1000]\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tFor each case of input you have to print the case number and the minimal cost.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e4\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e13 23 12\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e77 36 64\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e44 89 76\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e31 78 45\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e26 40 83\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e49 60 57\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003e13 89 99\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 137\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 96\u003c/span\u003e\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tUse simple DP\u003c/p\u003e"}}]}