{"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\u003eSummer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job in a shop as an assistant.\u003c/p\u003e\u003cp\u003eShop, where Noora is working, has a plan on the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e days. For each day sales manager knows exactly, that in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e products will be put up for sale and exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e clients will come to the shop that day. Also, the manager is sure, that everyone, who comes to the shop, buys exactly one product or, if there aren\u0027t any left, leaves the shop without buying anything. Moreover, due to the short shelf-life of the products, manager established the following rule: if some part of the products left on the shelves at the end of the day, that products aren\u0027t kept on the next day and are sent to the dump.\u003c/p\u003e\u003cp\u003eFor advertising purposes manager offered to start a sell-out in the shop. He asked Noora to choose any \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e days from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e next for sell-outs. On each of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e chosen days the number of products were put up for sale would be doubled. Thus, if on \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day shop planned to put up for sale \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e products and Noora has chosen this day for sell-out, shelves of the shop would keep \u003cspan class\u003d\"tex-span\"\u003e2·\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e products. Consequently, there is an opportunity to sell two times more products on days of sell-out.\u003c/p\u003e\u003cp\u003eNoora\u0027s task is to choose \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e days to maximize total number of sold products. She asks you to help her with such a difficult problem.\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\u003ef\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e, 0 ≤ \u003ci\u003ef\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e)\u003c/span\u003e denoting the number of days in shop\u0027s plan and the number of days that Noora has to choose for sell-out.\u003c/p\u003e\u003cp\u003eEach line of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e subsequent lines contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(0 ≤ \u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e)\u003c/span\u003e denoting the number of products on the shelves of the shop on the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day and the number of clients that will come to the shop on \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer denoting the maximal number of products that shop can sell.\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\u003e4 2\n2 1\n3 5\n2 3\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\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\u003e4 1\n0 2\n0 3\n3 5\n0 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\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 example we can choose days with numbers \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e for sell-out. In this case new numbers of products for sale would be equal to \u003cspan class\u003d\"tex-span\"\u003e[2, 6, 2, 2]\u003c/span\u003e respectively. So on the first day shop will sell \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e product, on the second\u0026nbsp;— \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, on the third\u0026nbsp;— \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, on the fourth\u0026nbsp;— \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. In total \u003cspan class\u003d\"tex-span\"\u003e1 + 5 + 2 + 2 \u003d 10\u003c/span\u003e product units.\u003c/p\u003e\u003cp\u003eIn the second example it is possible to sell \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e products, if you choose third day for sell-out.\u003c/p\u003e"}}]}