{"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\u003eFox Ciel is playing a card game with her friend Jiro.\u003c/p\u003e\u003cp\u003eJiro has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e cards, each one has two attributes: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eposition\u003c/i\u003e\u003c/span\u003e (Attack or Defense) and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estrength\u003c/i\u003e\u003c/span\u003e. Fox Ciel has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e cards, each one has these two attributes too. It\u0027s known that position of all Ciel\u0027s cards is Attack.\u003c/p\u003e\u003cp\u003eNow is Ciel\u0027s battle phase, Ciel can do the following operation many times:\u003c/p\u003e\u003col\u003e \u003cli\u003e Choose one of her cards \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e. This card mustn\u0027t be chosen before. \u003c/li\u003e\u003cli\u003e If Jiro has no alive cards at that moment, he gets the damage equal to (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e\u0027s strength). Otherwise, Ciel needs to choose one Jiro\u0027s alive card \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e, then: \u003cul\u003e \u003cli\u003e If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e\u0027s position is Attack, then (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e\u0027s strength) \u003cspan class\u003d\"tex-span\"\u003e ≥ \u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e\u0027s strength) must hold. After this attack, card \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e dies, and Jiro gets the damage equal to (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e\u0027s strength) - (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e\u0027s strength). \u003c/li\u003e\u003cli\u003e If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e\u0027s position is Defense, then (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e\u0027s strength) \u003cspan class\u003d\"tex-span\"\u003e \u0026gt; \u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e\u0027s strength) must hold. After this attack, card \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e dies, but Jiro gets no damage. \u003c/li\u003e\u003c/ul\u003e \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eCiel can end her battle phase at any moment (so, she can use not all her cards). Help the Fox to calculate the maximal sum of damage Jiro can get.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \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, \u003ci\u003em\u003c/i\u003e ≤ 100\u003c/span\u003e) — the number of cards Jiro and Ciel have.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains a string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eposition\u003c/i\u003e\u003c/span\u003e and an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estrength\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(0 ≤ \u003ci\u003estrength\u003c/i\u003e ≤ 8000)\u003c/span\u003e — the position and strength of Jiro\u0027s current card. Position is the string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eATK\u003c/span\u003e\" for attack, and the string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eDEF\u003c/span\u003e\" for defense.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estrength\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003estrength\u003c/i\u003e ≤ 8000\u003c/span\u003e) — the strength of Ciel\u0027s current card.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput an integer: the maximal damage Jiro can get.\u003c/p\u003e"}},{"title":"Examples","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 3\nATK 2000\nDEF 1700\n2500\n2500\n2500\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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 4\nATK 10\nATK 100\nATK 1000\n1\n11\n101\n1001\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e992\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e2 4\nDEF 0\nATK 0\n0\n0\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, Ciel has 3 cards with same \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estrength\u003c/i\u003e\u003c/span\u003e. The best strategy is as follows. First she uses one of these 3 cards to attack \"ATK 2000\" card first, this attack destroys that card and Jiro gets \u003cspan class\u003d\"tex-span\"\u003e2500 - 2000 \u003d 500\u003c/span\u003e damage. Then she uses the second card to destroy the \"DEF 1700\" card. Jiro doesn\u0027t get damage that time. Now Jiro has no cards so she can use the third card to attack and Jiro gets \u003cspan class\u003d\"tex-span\"\u003e2500\u003c/span\u003e damage. So the answer is \u003cspan class\u003d\"tex-span\"\u003e500 + 2500 \u003d 3000\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second test case, she should use the \"1001\" card to attack the \"ATK 100\" card, then use the \"101\" card to attack the \"ATK 10\" card. Now Ciel still has cards but she can choose to end her battle phase. The total damage equals \u003cspan class\u003d\"tex-span\"\u003e(1001 - 100) + (101 - 10) \u003d 992\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the third test case note that she can destroy the \"ATK 0\" card by a card with strength equal to 0, but she can\u0027t destroy a \"DEF 0\" card with that card.\u003c/p\u003e"}}]}