{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRick và đồng nghiệp của anh ấy đã tạo ra một công thức phóng xạ mới và rất nhiều kẻ xấu đang truy đuổi họ. Vì vậy Rick muốn để lại di sản của mình cho Morty trước khi những kẻ xấu bắt được họ.\u003c/p\u003e\u003cp\u003eCó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e hành tinh trong vũ trụ của họ được đánh số từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. Rick đang ở hành tinh số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e (trái đất) và anh ấy không biết Morty ở đâu. Như chúng ta đã biết, Rick sở hữu một khẩu súng cổng. Với khẩu súng này, anh ấy có thể mở cổng một chiều từ hành tinh anh ấy đang ở đến bất kỳ hành tinh nào khác (bao gồm cả hành tinh đó). Nhưng có giới hạn trên khẩu súng này vì anh ấy vẫn đang sử dụng phiên bản dùng thử miễn phí của nó.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/3b0b9090a8511052603466e16730af78?v\u003d1715342979\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eMặc định, anh ấy không thể mở bất kỳ cổng nào bằng khẩu súng này. Có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e kế hoạch trên trang web bán những khẩu súng này. Mỗi lần bạn mua một kế hoạch, bạn chỉ có thể sử dụng nó một lần nhưng bạn có thể mua lại nếu bạn muốn sử dụng nó nhiều lần.\u003c/p\u003e\u003cp\u003eCác kế hoạch trên trang web có ba loại:\u003c/p\u003e\u003col\u003e \u003cli\u003e Với một kế hoạch của loại này, bạn có thể mở một cổng từ hành tinh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e đến hành tinh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Với một kế hoạch của loại này, bạn có thể mở một cổng từ hành tinh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e đến bất kỳ hành tinh nào có chỉ số trong phạm vi \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Với một kế hoạch của loại này, bạn có thể mở một cổng từ bất kỳ hành tinh nào có chỉ số trong phạm vi \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e đến hành tinh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eRick không biết Morty ở đâu, nhưng Unity sẽ thông báo cho anh ấy và anh ấy muốn chuẩn bị khi tìm thấy và bắt đầu hành trình ngay lập tức. Vì vậy, đối với mỗi hành tinh (bao gồm cả trái đất), anh ấy muốn biết số tiền tối thiểu mà anh ấy cần để đi từ trái đất đến hành tinh đó.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của đầu vào chứa ba số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — số lượng hành tinh, số lượng kế hoạch và chỉ số của trái đất tương ứng.\u003c/p\u003e\u003cp\u003eCác dòng tiếp theo chứa các kế hoạch. Mỗi dòng bắt đầu bằng một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e, loại của kế hoạch đó (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e ≤ 3\u003c/span\u003e). Nếu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d 1\u003c/span\u003e thì nó được theo sau bởi ba số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e trong đó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e là chi phí của kế hoạch đó (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e, \u003ci\u003eu\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). Nếu không thì nó được theo sau bởi bốn số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e trong đó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e là chi phí của kế hoạch đó (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eTrong dòng đầu tiên và duy nhất của đầu ra, in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e số nguyên cách nhau bởi dấu cách. Số thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e sẽ là số tiền tối thiểu để đi từ trái đất đến hành tinh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, hoặc \u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003e nếu không thể đến được hành tinh đó.\u003c/p\u003e"}},{"title":"Ví dụ","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\u003e3 5 1\n2 3 2 3 17\n2 3 2 2 16\n2 2 2 3 3\n3 3 1 1 12\n1 3 3 17\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 28 12 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\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 3 1\n3 4 1 3 12\n2 2 3 4 10\n1 2 4 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 -1 -1 12 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong bài kiểm tra mẫu đầu tiên, Rick có thể mua kế hoạch thứ \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e một lần và sau đó kế hoạch thứ \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e để đến hành tinh số \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e.\u003c/p\u003e"}}]}