{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp align\u003d\"left\"\u003e\r\nTo reach the treasure, \u003cb\u003eJones\u003c/b\u003e has to pass through the \u003cb\u003e\"Room of Death\"\u003c/b\u003e. The floor of this room is a square with side \u003cb\u003e120\u003c/b\u003e units. It is laid with square tiles of dimensions \u003cb\u003e{1 X 1}\u003c/b\u003e arranged into a grid. But, at some places in the grid tiles are missing. As soon as the door to this room is opened poisonous gas starts coming out of these missing grid locations. The only escape from this gas is to completely cover these locations with planks lying outside the room. Each plank has dimensions \u003cb\u003e{120 X 1}\u003c/b\u003e and can only be placed parallel to either sides of the floor. Now \u003cb\u003eJones\u003c/b\u003e wants to minimize the damage to his health so that he has enough of it left for the treasure. He figures out that in order to achieve this he has to use the minimum number of planks possible. He also realises that even if the planks overlap, poisonous gas from the missing tiles can still be successfully blocked. Please help \u003cb\u003eJones\u003c/b\u003e in this task.\r\n\u003c/p\u003e\r\n\r\n\u003cp align\u003d\"center\"\u003e\r\n\u003c/p\u003e\u003ccenter\u003e\r\n\u003c/center\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\r\n\t\u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/43d6a1c4d3757fd4f68c6ef042a445e5?v\u003d1715276387\" width\u003d\"430\" height\u003d\"486\" border\u003d\"0\" alt\u003d\"Dungeon of Death: Tiles Uncovered\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\r\n\t\u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/c337805c9f2151b286b027645950f437?v\u003d1715276387\" width\u003d\"430\" height\u003d\"486\" border\u003d\"0\" alt\u003d\"Dungeon of Death: Tiles Covered\"\u003e\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003c/tbody\u003e\u003c/table\u003e \r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\r\n\u003cul\u003e \r\n\t\u003cli\u003e The first line of the input is a positive integer \u003cb\u003et \u0026lt;\u003d 20\u003c/b\u003e, denoting the number of rooms.\r\n\t\u003c/li\u003e\u003cli\u003e The descriptions for the t rooms follow one after the other.\r\n\t\u003c/li\u003e\u003cli\u003e \u003cb\u003eRoom Description:\u003c/b\u003e\r\n\t\t\u003cul\u003e \r\n\t\t\t\u003cli\u003e The first line of the room description is a positive integer \u003cb\u003en (n \u0026lt;\u003d 10010)\u003c/b\u003e, denoting the number of missing tile locations.\r\n\t\t\t\u003c/li\u003e\u003cli\u003e This is followed by the \u003cb\u003en\u003c/b\u003e lines, one for each missing tile location.\r\n\t\t\t\u003c/li\u003e\u003cli\u003e Each line contains two integers \u003cb\u003ex y (0 \u0026lt;\u003d x, y \u0026lt; 120)\u003c/b\u003e, separated by a single space, representing the co-ordinates of the missing tile location.\r\n\t\t\u003c/li\u003e\u003c/ul\u003e\r\n\u003c/li\u003e\u003c/ul\u003e \r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eThe output should consist of \u003cb\u003et\u003c/b\u003e lines, one for each room. The \u003cb\u003ek\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e line in the output should be an integer \u003cb\u003em\u003csub\u003ek\u003c/sub\u003e\u003c/b\u003e, the minimum number of planks needed for the \u003cb\u003ek\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e room.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003ctt\u003e\r\n\u003cp\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n\u003cbr\u003e2\r\n\u003cbr\u003e3\r\n\u003cbr\u003e1 0\r\n\u003cbr\u003e2 0\r\n\u003cbr\u003e3 0\r\n\u003cbr\u003e4\r\n\u003cbr\u003e1 1\r\n\u003cbr\u003e2 2\r\n\u003cbr\u003e3 3\r\n\u003cbr\u003e4 4\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n\u003cbr\u003e1\r\n\u003cbr\u003e4\r\n\u003c/p\u003e\r\n\u003c/tt\u003e\n\u003c/div\u003e"}}]}