{"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\u003eA popular reality show is recruiting a new cast for the third season! $$$n$$$ candidates numbered from $$$1$$$ to $$$n$$$ have been interviewed. The candidate $$$i$$$ has aggressiveness level $$$l_i$$$, and recruiting this candidate will cost the show $$$s_i$$$ roubles.\u003c/p\u003e\u003cp\u003eThe show host reviewes applications of all candidates from $$$i\u003d1$$$ to $$$i\u003dn$$$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $$$i$$$ is strictly higher than that of any \u003cspan class\u003d\"tex-font-style-bf\"\u003ealready accepted\u003c/span\u003e candidates, then the candidate $$$i$$$ will definitely be rejected. Otherwise the host may accept or reject this candidate at her own discretion. The host wants to choose the cast so that to maximize the total \u003cspan class\u003d\"tex-font-style-it\"\u003eprofit\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe show makes revenue as follows. For each aggressiveness level $$$v$$$ a corresponding profitability value $$$c_v$$$ is specified, which can be positive as well as negative. All recruited participants enter the stage one by one by increasing of their indices. When the participant $$$i$$$ enters the stage, events proceed as follows:\u003c/p\u003e\u003cul\u003e \u003cli\u003e The show makes $$$c_{l_i}$$$ roubles, where $$$l_i$$$ is initial aggressiveness level of the participant $$$i$$$. \u003c/li\u003e\u003cli\u003e If there are two participants with the same aggressiveness level on stage, they immediately start a fight. The outcome of this is:\u003cul\u003e \u003cli\u003e the defeated participant is hospitalized and leaves the show. \u003c/li\u003e\u003cli\u003e aggressiveness level of the victorious participant is increased by one, and the show makes $$$c_t$$$ roubles, where $$$t$$$ is the new aggressiveness level. \u003c/li\u003e\u003c/ul\u003e\u003c/li\u003e\u003cli\u003e The fights continue until all participants on stage have distinct aggressiveness levels. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIt is allowed to select an empty set of participants (to choose neither of the candidates).\u003c/p\u003e\u003cp\u003eThe host wants to recruit the cast so that the total profit is maximized. The profit is calculated as the total revenue from the events on stage, less the total expenses to recruit all accepted participants (that is, their total $$$s_i$$$). Help the host to make the show as profitable as possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n, m \\le 2000$$$) — the number of candidates and an upper bound for initial aggressiveness levels.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$l_i$$$ ($$$1 \\le l_i \\le m$$$) — initial aggressiveness levels of all candidates.\u003c/p\u003e\u003cp\u003eThe third line contains $$$n$$$ integers $$$s_i$$$ ($$$0 \\le s_i \\le 5000$$$) — the costs (in roubles) to recruit each of the candidates.\u003c/p\u003e\u003cp\u003eThe fourth line contains $$$n + m$$$ integers $$$c_i$$$ ($$$|c_i| \\le 5000$$$) — profitability for each aggrressiveness level.\u003c/p\u003e\u003cp\u003eIt is guaranteed that aggressiveness level of any participant can never exceed $$$n + m$$$ under given conditions.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the largest profit of the show.\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\u003e5 4\n4 3 1 2 1\n1 2 1 2 1\n1 2 3 4 5 6 7 8 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\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 2\n1 2\n0 0\n2 1 -100 -100\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"}},{"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\u003e5 4\n4 3 2 1 1\n0 2 6 7 4\n12 12 12 6 -3 -5 3 10 -4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e62\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 sample case it is optimal to recruit candidates $$$1, 2, 3, 5$$$. Then the show will pay $$$1 + 2 + 1 + 1 \u003d 5$$$ roubles for recruitment. The events on stage will proceed as follows:\u003c/p\u003e\u003cul\u003e \u003cli\u003e a participant with aggressiveness level $$$4$$$ enters the stage, the show makes $$$4$$$ roubles; \u003c/li\u003e\u003cli\u003e a participant with aggressiveness level $$$3$$$ enters the stage, the show makes $$$3$$$ roubles; \u003c/li\u003e\u003cli\u003e a participant with aggressiveness level $$$1$$$ enters the stage, the show makes $$$1$$$ rouble; \u003c/li\u003e\u003cli\u003e a participant with aggressiveness level $$$1$$$ enters the stage, the show makes $$$1$$$ roubles, a fight starts. One of the participants leaves, the other one increases his aggressiveness level to $$$2$$$. The show will make extra $$$2$$$ roubles for this. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eTotal revenue of the show will be $$$4 + 3 + 1 + 1 + 2\u003d11$$$ roubles, and the profit is $$$11 - 5 \u003d 6$$$ roubles.\u003c/p\u003e\u003cp\u003eIn the second sample case it is impossible to recruit both candidates since the second one has higher aggressiveness, thus it is better to recruit the candidate $$$1$$$.\u003c/p\u003e"}}]}