{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e贝西听说一场特殊的流星雨即将来袭;报道称这些流星将撞击地球并摧毁它们碰到的一切。为了自身安全,她发誓要找到一个安全的地点(一个永远不会被流星摧毁的地方)。她目前正在坐标平面的原点处吃草,并希望在前往新的、更安全的地点的途中避免被流星摧毁。\u003c/p\u003e\u003cp\u003e报道称会有 \u003ci\u003eM\u003c/i\u003e 颗流星(1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 50,000)撞击,其中第 \u003ci\u003ei\u003c/i\u003e 颗流星将在时间 \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e(0 ≤ \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 1,000)时撞击到点(\u003ci\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e)(0 ≤ \u003ci\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 300; 0 ≤ \u003ci\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 300)。每颗流星摧毁它撞击的点,以及四个直角相邻的格点。\u003c/p\u003e\u003cp\u003e贝西在时间 0 离开原点,可以以每秒一单位的速度沿着第一象限内的轴线平行移动到任何尚未被流星摧毁的(通常是 4 个)相邻直角点。她不能在任何大于或等于被摧毁的时间的点停留。\u003c/p\u003e\u003cp\u003e确定贝西到达安全地点所需的最短时间。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e* 第 1 行: 一个整数: \u003ci\u003eM\u003c/i\u003e\u003cbr\u003e* 第 2 行到第 \u003ci\u003eM\u003c/i\u003e+1 行: 第 \u003ci\u003ei\u003c/i\u003e+1 行包含三个用空格分隔的整数: \u003ci\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eY\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, 和 \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e* 第 1 行: 贝西到达安全地点所需的最短时间,如果不可能则输出 -1。\u003c/p\u003e"}},{"title":"示例","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\u003e4\r\n0 0 2\r\n2 1 2\r\n1 1 2\r\n0 3 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}