{"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\u003eJoaozao and Nicoleta are planning to buy some pies at the local market. There are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e different types of pies and Joaozao only buys pies of the types that are on his list of preferred pie types. The same goes for Nicoleta, who only buys pies of the types that are on his list of preferred pie types. It\u0027s guaranteed that every type of pie appears on at least one list of preferences.\u003c/p\u003e\u003cp\u003eThe local market is doing a special pie sale. Because of this, all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e pies are lined up in a row. The first pie in the row is of type \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, the second pie is of type \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e and so on until the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e-th pie that is of type \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. It is guaranteed that the market sells all types of pies (i.e. each one of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e types of pies will appear at least once in this row). The special promotion of this sale was: if the same person buys pie \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and pie \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e is the position of the pie in the row, this person gets \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e candies.\u003c/p\u003e\u003cp\u003ePies of the same type cannot be bought by different people (i.e. if Joaozao buys one pie of type \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e, then he has to buy all other pies of the same type \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eJoaozao and Nicoleta decided they will buy all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e pies in the row and they want to maximize the total amount of candies they will earn. Given the lists of preferences for each one of them, the type of the pies in the row and the amount of candies that is earned for each pair of consecutive pies, can you tell what is the maximum total amount of candies they can get?\u003c/p\u003e\u003cp\u003eThe total amount of candies is the sum of the candies earned by each of them.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains four integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003eK\u003c/i\u003e ≤ 500\u003c/span\u003e), \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e), \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e ≤ \u003ci\u003eK\u003c/i\u003e\u003c/span\u003e) indicating, respectively, the number of types of pies, the number of pies in the row of pies, the size of Joaozao\u0027s preference list and the size of Nicoleta\u0027s preference list. Pie types are numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e integers, the types of pies that Joaozao prefers.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e integers, the types of pies that Nicoleta prefers.\u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that all the different types of pies will appear in at least one list of preferences.\u003c/p\u003e\u003cp\u003eThe fourth line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e integers. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th integer of this line indicates the type of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th pie of the row, as described in the statement. Each of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e types of pie will appear at least once.\u003c/p\u003e\u003cp\u003eThe fifth and last line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e - 1\u003c/span\u003e integers. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th integer of this line \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eg\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\"\u003e1 ≤ \u003ci\u003eg\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e) corresponds to the amount of candies earned when buying the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th and the \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ei\u003c/i\u003e + 1)\u003c/span\u003e-th pie.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer indicating the maximum total amount of candies that Joaozao and Nicoleta can earn.\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 6 1 3\n1\n2 3 4\n1 3 2 2 4 1\n1 2 4 8 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\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\u003e4 10 3 3\n1 2 3\n2 3 4\n1 2 3 4 3 1 2 4 3 1\n1 1 5 5 2 2 1 5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\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 case, to maximize the total amount of candies earned, Joaozao should buy the pies in positions 1 and 6 (1-indexed). Nicoleta should buy the rest.\u003c/p\u003e\u003cp\u003eIn the second case, the pies that Joaozao should buy are in positions 1, 2, 6, 7 and 10. Nicoleta should buy the pies in positions 3, 4, 5, 8, 9.\u003c/p\u003e"}}]}