{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nAs mentioned in the problem \"Couples\", so many new words appear on the internet. Another special one is \"Damn Couples\", a club which consists of people who have failed on love affairs and decide not to start a relationship. (If you want to know more words, just turn to a search engine.)\n\u003c/p\u003e\n\u003cp align\u003d\"center\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/2e87e1b56e9bc461b68ccb2afe7d74d1?v\u003d1715287427\" alt\u003d\"Damn couples!\"\u003e\n\u003c/p\u003e\n\u003cp\u003e\nWe have a group of people in the club, and everyday they sit there in one line in a fixed order, doing nothing. Life in the club is indeed boring, especially for the leader Wyest, and one day she invented a game. She first makes up a list of imaginary \"8g\"s among the members, every \"8g\" is between two persons, then publishes the list. Each minute she chooses one \"8g\" from the list and announces it to be true, until all \"8g\"s in the list have been announced. She will not 8g the same two persons more than once.\n\u003c/p\u003e\n\u003cp\u003e\nIn a single minute, the following things may happen.\n\u003c/p\u003e\n\u003cp\u003e\n1. If the two persons involved in the \"8g\" are sitting next to each other, \u003cem\u003eone\u003c/em\u003e of them will speak out the \"Damn couples!\" slogan, then stand up and leave the table. Notice that leaving doesn\u0027t prevent him/her from possible future \"8g\"s.\n\u003cbr\u003e\n2. If the \u003cem\u003ei\u003c/em\u003eth person left, the \u003cem\u003e(i-1)\u003c/em\u003eth and the \u003cem\u003e(i+1)\u003c/em\u003eth are considered to be next to each other.\n\u003c/p\u003e\n\u003cp\u003e\nOn the other hand, Wyest wouldn\u0027t like to see people become too few since she likes it to be noisy. All the members know this, however, to show their loyalty for the club, they try to make leaving people as \u003cem\u003emany\u003c/em\u003e as possible, based on the already announced \"8g\"s and those not yet to be. Wyest also knows what they\u0027re planning, so now she wants to know at most how many people can remain, if she carefully chooses the \"8g\" to announce each minute. Could you help her find it out?\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nThe first line of each case will contain two integers \u003cem\u003en\u003c/em\u003e (2 \u0026lt;\u003d \u003cem\u003en\u003c/em\u003e \u0026lt;\u003d 500) and \u003cem\u003em\u003c/em\u003e (0 \u0026lt;\u003d \u003cem\u003em\u003c/em\u003e \u0026lt;\u003d C(\u003cem\u003en\u003c/em\u003e, 2)), indicating the number of persons and the number of \"8g\"s in the list. People are indexed from \u003cem\u003e0\u003c/em\u003e to \u003cem\u003en - 1\u003c/em\u003e and they always sit in increasing order. The following \u003cem\u003em\u003c/em\u003e lines each contains two integers \u003cem\u003ea\u003c/em\u003e and \u003cem\u003eb\u003c/em\u003e, meaning a \"8g\" between \u003cem\u003ea\u003c/em\u003e and \u003cem\u003eb\u003c/em\u003e.\nProceed to the end of file.\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nFor each case, print one line containing the maximum number of people that can remain in total.\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n\u003c/p\u003e\u003cpre\u003e3 2\n0 1\n1 2\n3 1\n0 2\u003c/pre\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n\u003c/p\u003e\u003cpre\u003e1\n3\u003c/pre\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eHint\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\nIn the first case, no matter in what order the \"8g\"s are announced, the \u003cem\u003e1\u003c/em\u003est person wouldn\u0027t leave first. In the second case, the \u003cem\u003e0\u003c/em\u003eth person and the \u003cem\u003e2\u003c/em\u003end person didn\u0027t sit together, so all of the three remain.\n\u003c/p\u003e\n\n\u003c!--\nfor ZOJ Monthly, February 2009\n\nvim: ft\u003dhtml\n--\u003e\n"}}]}