{"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\u003eRalph sẽ đi thu thập nấm trong Rừng Nấm.\u003c/p\u003e\u003cp\u003eCó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e con đường hướng đi kết nối \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e cây trong Rừng Nấm. Trên mỗi con đường, sẽ mọc một số nấm. Khi Ralph đi qua một con đường, anh ta sẽ thu thập tất cả các nấm trên con đường đó. Rừng Nấm có một mảnh đất màu mỡ ma thuật nơi nấm mọc với tốc độ tuyệt vời. Nấm mới sẽ mọc lại ngay sau khi Ralph kết thúc việc thu thập nấm trên một con đường. Cụ thể hơn, sau khi Ralph đi qua một con đường lần thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, sẽ mọc lại \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e nấm ít hơn so với trước lần đi qua đó. Nghĩa là, nếu ban đầu có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e nấm trên một con đường, thì Ralph sẽ thu thập \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e nấm lần đầu, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e - 1\u003c/span\u003e nấm lần thứ hai, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e - 1 - 2\u003c/span\u003e nấm lần thứ ba, và cứ thế. Tuy nhiên, số lượng nấm không bao giờ ít hơn \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eVí dụ, giả sử có \u003cspan class\u003d\"tex-span\"\u003e9\u003c/span\u003e nấm trên một con đường ban đầu. Số lượng nấm có thể thu thập từ con đường đó là \u003cspan class\u003d\"tex-span\"\u003e9\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e khi Ralph đi qua từ lần thứ nhất đến lần thứ tư. Từ lần thứ năm trở đi, Ralph sẽ không thể thu thập nấm từ con đường đó nữa (nhưng vẫn có thể đi qua).\u003c/p\u003e\u003cp\u003eRalph quyết định bắt đầu từ cây \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e. Anh ta có thể thu thập bao nhiêu nấm chỉ bằng các con đường đã mô tả?\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e), đại diện cho số cây và số con đường hướng đi trong Rừng Nấm, tương ứng.\u003c/p\u003e\u003cp\u003eMỗi trong số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dòng tiếp theo chứa ba số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e8\u003c/sup\u003e\u003c/span\u003e), biểu thị một con đường dẫn từ cây \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e đến cây \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e với \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e nấm ban đầu. Có thể có con đường dẫn từ một cây đến chính nó, và nhiều con đường giữa cùng một cặp cây.\u003c/p\u003e\u003cp\u003eDòng cuối cùng chứa một số nguyên duy nhất \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) - vị trí bắt đầu của Ralph.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn một số nguyên biểu thị số lượng nấm tối đa mà Ralph có thể thu thập trong chuyến đi của mình.\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\u003e2 2\n1 2 4\n2 1 4\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\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\u003e3 3\n1 2 4\n2 3 3\n1 3 8\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\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 ví dụ đầu tiên, Ralph có thể đi ba lần trên vòng tròn và thu thập \u003cspan class\u003d\"tex-span\"\u003e4 + 4 + 3 + 3 + 1 + 1 \u003d 16\u003c/span\u003e nấm. Sau đó, sẽ không còn nấm nào cho Ralph thu thập nữa.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, Ralph có thể đi đến cây \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e và thu thập \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e nấm trên con đường từ cây \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến cây \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e.\u003c/p\u003e"}}]}