{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eGeorg\u0027s new MP3 player has many interesting features, one of them being the key lock. All the keys are locked after more than \u003cem\u003eT\u003c/em\u003e seconds of inactivity. After the key lock is engaged, no key performs its original function, but if any key is pressed, the key lock is disengaged.\u003c/p\u003e\r\n\u003cp\u003eFor example, assume that \u003cem\u003eT\u003c/em\u003e \u003d 5 and the player is currently locked. Georg presses the key \u003cem\u003eA\u003c/em\u003e, waits for 3 seconds, presses the key \u003cem\u003eB\u003c/em\u003e, waits for 5 seconds, presses \u003cem\u003eC\u003c/em\u003e, waits for 6 seconds, and presses \u003cem\u003eD\u003c/em\u003e. In this case only the keys \u003cem\u003eB\u003c/em\u003e and \u003cem\u003eC\u003c/em\u003e perform their regular functions. Note that the keys became locked between \u003cem\u003eC\u003c/em\u003e and \u003cem\u003eD\u003c/em\u003e was pressed.\u003c/p\u003e\r\n\u003cp\u003eSound level of the MP3 player is controlled by the \u003ctt\u003e+\u003c/tt\u003e and \u003ctt\u003e-\u003c/tt\u003e keys, increasing and decreasing volume by 1 unit respectively. The sound level is an integer between 0 and \u003cem\u003eV\u003c/em\u003e\u003csub\u003e\u003cem\u003em\u003c/em\u003e\u003cem\u003ea\u003c/em\u003e\u003cem\u003ex\u003c/em\u003e\u003c/sub\u003e. Pressing the \u003ctt\u003e+\u003c/tt\u003e key at volume \u003cem\u003eV\u003c/em\u003e\u003csub\u003e\u003cem\u003em\u003c/em\u003e\u003cem\u003ea\u003c/em\u003e\u003cem\u003ex\u003c/em\u003e\u003c/sub\u003e or pressing the \u003ctt\u003e-\u003c/tt\u003e key at volume 0 leaves the volume unchanged.\u003c/p\u003e\r\n\r\n\u003ch3\u003eTask specification\u003c/h3\u003e\r\n\u003cp\u003eGeorg does not know the value of \u003cem\u003eT\u003c/em\u003e. He wanted to find it by an experiment. Starting with a locked keyboard, he pressed a sequence of \u003cem\u003eN\u003c/em\u003e \u003ctt\u003e+\u003c/tt\u003e and \u003ctt\u003e-\u003c/tt\u003e keys. At the end of the experiment Georg read the final volume from the player\u0027s display. Unfortunately, he forgot to note the volume before his first keypress. For the purpose of this task, the unknown initial volume will be denoted \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e and the known final volume will be denoted \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e.\u003c/p\u003e\r\n\u003cp\u003eYou are given the value \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e and a list of keystrokes in the order in which Georg made them. For each key, you are given the type of the key (\u003ctt\u003e+\u003c/tt\u003e or \u003ctt\u003e-\u003c/tt\u003e) and the number of seconds from the beginning of the experiment to the moment when the key was pressed. The task is to find the largest possible \u003cstrong\u003einteger\u003c/strong\u003e value of \u003cem\u003eT\u003c/em\u003e which is consistent with the outcome of the experiment.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains three space-separated integers \u003cem\u003eN\u003c/em\u003e, \u003cem\u003eV\u003c/em\u003e\u003csub\u003e\u003cem\u003em\u003c/em\u003e\u003cem\u003ea\u003c/em\u003e\u003cem\u003ex\u003c/em\u003e\u003c/sub\u003e and \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e (0 ≤ V\u003csub\u003e2\u003c/sub\u003e ≤ V\u003csub\u003emax\u003c/sub\u003e). Each of the next \u003cem\u003eN\u003c/em\u003e lines contains a description of one key in the sequence: a character \u003ctt\u003e+\u003c/tt\u003e or \u003ctt\u003e-\u003c/tt\u003e, a space and an integer \u003cem\u003eC\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e (0 ≤ C\u003csub\u003ei\u003c/sub\u003e≤ 2 x 10\u003csup\u003e9\u003c/sup\u003e), the number of seconds from the beginning of the experiment. You may assume that the keypresses are in sorted order and that all times are distinct (i.e., \u003cem\u003eC\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e \u0026lt; \u003cem\u003eC\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e + 1\u003c/sub\u003e for all 1 ≤ i \u0026lt; N).\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eIf \u003cem\u003eT\u003c/em\u003e can be arbitrarily large, output a single line containing the word \"\u003ctt\u003einfinity\u003c/tt\u003e\" (quotes for clarity).\u003c/p\u003e\r\n\u003cp\u003eOtherwise, output a single line containing two integers \u003cem\u003eT\u003c/em\u003e and \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e separated by a single space.\u003c/p\u003e\r\n\u003cp\u003eThe values must be such that carrying out the experiment with locking time \u003cem\u003eT\u003c/em\u003e starting at volume \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e gives the final volume \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e. If there are multiple possible answers, output the one with the largest \u003cem\u003eT\u003c/em\u003e; if there are still multiple possible answers, output the one with the largest \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e.\u003c/p\u003e\r\n\u003cp\u003e(Note that at least one solution always exists: for \u003cem\u003eT\u003c/em\u003e \u003d 0 none of the keys performs its action, so it suffices to take \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e \u003d \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e.)\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003eYou may assume that 2 ≤ N ≤ 100000 and 2 ≤ V\u003csub\u003emax\u003c/sub\u003e ≤ 5000.\u003c/p\u003e\r\n\u003cp\u003eIn test cases worth 40 points N ≤ 4000.\u003c/p\u003e\r\n\u003cp\u003eIn test cases worth 70 points N x V\u003csub\u003emax\u003c/sub\u003e ≤ 400000.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExamples\u003c/h3\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003e6 4 3\u003cbr\u003e- 0\u003cbr\u003e+ 8\u003cbr\u003e+ 9\u003cbr\u003e+ 13\u003cbr\u003e- 19\u003cbr\u003e- 24\u003cbr\u003e\u003c/pre\u003e\r\n\u003cp\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003e5 4\u003cbr\u003e\u003c/pre\u003e\r\n\u003cp\u003eFor \u003cem\u003eT\u003c/em\u003e \u003d 5 the keys perform the following actions: unlock, unlock, \u003ctt\u003e+\u003c/tt\u003e, \u003ctt\u003e+\u003c/tt\u003e, unlock, \u003ctt\u003e-\u003c/tt\u003e.\u003c/p\u003e\r\n\u003cp\u003eFor any \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e ∈; {2, 3, 4} we would get \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e \u003d 3. Note that the output contains the largest possible \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e.\u003c/p\u003e\r\n\u003cp\u003eFor \u003cem\u003eT\u003c/em\u003e ≥ 6 the last two keystrokes will both be active, hence it will be impossible to have \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e \u003d 3.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003e3 10 10\u003cbr\u003e+ 1\u003cbr\u003e+ 2\u003cbr\u003e+ 47\u003cbr\u003e\u003c/pre\u003e\r\n\u003cp\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cpre\u003einfinity\u003cbr\u003e\u003c/pre\u003e\r\n\u003cp\u003eIf \u003cem\u003eV\u003c/em\u003e\u003csub\u003e1\u003c/sub\u003e \u003d 10 then for any \u003cem\u003eT\u003c/em\u003e we\u0027ll have \u003cem\u003eV\u003c/em\u003e\u003csub\u003e2\u003c/sub\u003e \u003d 10.\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}