{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e8b2611c1a7dc2baabc309ca5155597e?v\u003d1719488757\" alt\u003d\"/problems/outing/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eOrganising a group trip for the elderly can be a daunting\n task... Not least because of the fussy participants, each of\n whom will only make the trip on condition that some other\n participant also comes.\u003c/p\u003e\n\n \u003cp\u003eAfter some effort, you have taken from each of your\n participants a number, indicating that this participant will\n refuse to join the excursion unless the participant with that\n number also joins– the less choosy simply give their own\n number. This would be easy enough to resolve (just send all of\n them) but the bus you are going to use during the trip has only\n a fixed number of places.\u003c/p\u003e\n\n \u003ch2\u003eTask\u003c/h2\u003e\n\n \u003cp\u003eGiven the preferences of all participants, find the maximum\n number of participants that can join.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq k \\leq n \\leq 1\\, 000$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e denotes the total number of\n participants and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e\n denotes the number of places on the bus.\u003c/p\u003e\n\n \u003cp\u003eThe second line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$x_{i}$\u003c/span\u003e for \u003cspan class\u003d\"tex2jax_process\"\u003e$i\u003d1,2,\\ldots ,n$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq x_ i \\leq n$\u003c/span\u003e. The meaning of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e is that the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th participant will\n refuse to join the excursion unless the \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e-th participant also joins.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput one integer: the maximum number of participants that\n can join the excursion, so that all the participants’\n preferences are obeyed and the capacity of the bus is not\n exceeded.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 4\n1 2 3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e12 3\n2 3 4 5 6 7 4 7 8 8 12 12\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\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 4\n2 3 1 5 4\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\n\u003c/body\u003e\n "}}]}