{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eKhoa Y của Đại học Nhà nước Berland vừa hoàn thành chiến dịch tuyển sinh của mình. Như thường lệ, khoảng $$$80\\%$$$ số ứng viên là nữ và phần lớn trong số họ sẽ sống tại ký túc xá của trường trong $$$4$$$ năm tiếp theo (hy vọng).\u003c/p\u003e\u003cp\u003eKý túc xá bao gồm $$$n$$$ phòng và một con chuột duy nhất! Các cô gái quyết định đặt bẫy chuột trong một số phòng để loại bỏ con quái vật kinh hoàng đó. Việc đặt bẫy trong phòng số $$$i$$$ tốn $$$c_i$$$ burles. Các phòng được đánh số từ $$$1$$$ đến $$$n$$$.\u003c/p\u003e\u003cp\u003eChuột không ngồi yên tại một chỗ mọi lúc, nó luôn chạy. Nếu nó ở phòng $$$i$$$ vào giây thứ $$$t$$$ thì nó sẽ chạy đến phòng $$$a_i$$$ vào giây thứ $$$t + 1$$$ mà không ghé qua bất kỳ phòng nào khác ở giữa ($$$i \u003d a_i$$$ có nghĩa là chuột sẽ không rời khỏi phòng $$$i$$$). Bắt đầu từ giây thứ $$$0$$$. Nếu chuột ở trong một phòng có bẫy chuột, thì chuột sẽ bị bắt vào bẫy này.\u003c/p\u003e\u003cp\u003eĐiều đó sẽ dễ dàng nếu các cô gái thực sự biết chuột ở đâu. Thật không may, điều đó không phải là trường hợp, chuột có thể ở bất kỳ phòng nào từ $$$1$$$ đến $$$n$$$ vào giây thứ $$$0$$$.\u003c/p\u003e\u003cp\u003eTổng số burles tối thiểu mà các cô gái có thể tiêu để đặt bẫy và đảm bảo rằng chuột sẽ bị bắt dù chuột bắt đầu từ phòng nào?\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa một số nguyên $$$n$$$ ($$$1 \\le n \\le 2 \\cdot 10^5$$$) — số phòng trong ký túc xá.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa $$$n$$$ số nguyên $$$c_1, c_2, \\dots, c_n$$$ ($$$1 \\le c_i \\le 10^4$$$) — $$$c_i$$$ là chi phí đặt bẫy ở phòng số $$$i$$$.\u003c/p\u003e\u003cp\u003eDòng thứ ba chứa $$$n$$$ số nguyên $$$a_1, a_2, \\dots, a_n$$$ ($$$1 \\le a_i \\le n$$$) — $$$a_i$$$ là phòng mà chuột sẽ chạy đến vào giây tiếp theo sau khi ở phòng $$$i$$$.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn một số nguyên duy nhất — tổng số burles tối thiểu mà các cô gái có thể tiêu để đặt bẫy và đảm bảo rằng chuột sẽ bị bắt dù chuột bắt đầu từ phòng nào.\u003c/p\u003e"}},{"title":"Ví dụ 1","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\u003e5\n1 2 3 2 10\n1 3 4 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 2","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\n1 10 2 10\n2 4 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 3","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\u003e7\n1 1 1 1 1 1 1\n2 2 2 3 6 7 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\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 ví dụ đầu tiên, đủ để đặt bẫy chuột ở các phòng $$$1$$$ và $$$4$$$. Nếu chuột bắt đầu từ phòng $$$1$$$ thì nó sẽ bị bắt ngay lập tức. Nếu chuột bắt đầu từ bất kỳ phòng nào khác thì cuối cùng nó sẽ đến phòng $$$4$$$.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, đủ để đặt bẫy chuột ở phòng $$$2$$$. Nếu chuột bắt đầu từ phòng $$$2$$$ thì nó sẽ bị bắt ngay lập tức. Nếu chuột bắt đầu từ bất kỳ phòng nào khác thì nó sẽ chạy đến phòng $$$2$$$ vào giây thứ $$$1$$$.\u003c/p\u003e\u003cp\u003eĐây là các con đường di chuyển của chuột từ các điểm khởi đầu khác nhau trong ví dụ thứ ba:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\rightarrow 2 \\rightarrow 2 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$2 \\rightarrow 2 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 2 \\rightarrow 2 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$4 \\rightarrow 3 \\rightarrow 2 \\rightarrow 2 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$5 \\rightarrow 6 \\rightarrow 7 \\rightarrow 6 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$6 \\rightarrow 7 \\rightarrow 6 \\rightarrow \\dots$$$; \u003c/li\u003e\u003cli\u003e $$$7 \\rightarrow 6 \\rightarrow 7 \\rightarrow \\dots$$$; \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eVậy đủ để đặt bẫy ở các phòng $$$2$$$ và $$$6$$$.\u003c/p\u003e"}}]}