{"raw_statement":[{"iden":"statement","content":"Joaozao and Nicoleta are planning to buy some pies at the local market. There are K 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's guaranteed that every type of pie appears on at least one list of preferences.\n\nThe local market is doing a special pie sale. Because of this, all N pies are lined up in a row. The first pie in the row is of type p1, the second pie is of type p2 and so on until the N-th pie that is of type pN. It is guaranteed that the market sells all types of pies (i.e. each one of the K types of pies will appear at least once in this row). The special promotion of this sale was: if the same person buys pie i and pie i + 1, where i is the position of the pie in the row, this person gets gi candies.\n\nPies of the same type cannot be bought by different people (i.e. if Joaozao buys one pie of type t, then he has to buy all other pies of the same type t).\n\nJoaozao and Nicoleta decided they will buy all N 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?\n\nThe total amount of candies is the sum of the candies earned by each of them.\n\nThe first line of the input contains four integers K (2 ≤ K ≤ 500), N (K ≤ N ≤ 103), A and B (1 ≤ A, B ≤ K) indicating, respectively, the number of types of pies, the number of pies in the row of pies, the size of Joaozao's preference list and the size of Nicoleta's preference list. Pie types are numbered from 1 to K.\n\nThe second line contains A integers, the types of pies that Joaozao prefers.\n\nThe third line contains B integers, the types of pies that Nicoleta prefers.\n\nIt's guaranteed that all the different types of pies will appear in at least one list of preferences.\n\nThe fourth line contains N integers. The i-th integer of this line indicates the type of the i-th pie of the row, as described in the statement. Each of the K types of pie will appear at least once.\n\nThe fifth and last line contains N - 1 integers. The i-th integer of this line gi (1 ≤ gi ≤ 103) corresponds to the amount of candies earned when buying the i-th and the (i + 1)-th pie.\n\nOutput a single integer indicating the maximum total amount of candies that Joaozao and Nicoleta can earn.\n\nIn 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.\n\nIn 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.\n\n"},{"iden":"input","content":"The first line of the input contains four integers K (2 ≤ K ≤ 500), N (K ≤ N ≤ 103), A and B (1 ≤ A, B ≤ K) indicating, respectively, the number of types of pies, the number of pies in the row of pies, the size of Joaozao's preference list and the size of Nicoleta's preference list. Pie types are numbered from 1 to K.The second line contains A integers, the types of pies that Joaozao prefers.The third line contains B integers, the types of pies that Nicoleta prefers.It's guaranteed that all the different types of pies will appear in at least one list of preferences.The fourth line contains N integers. The i-th integer of this line indicates the type of the i-th pie of the row, as described in the statement. Each of the K types of pie will appear at least once.The fifth and last line contains N - 1 integers. The i-th integer of this line gi (1 ≤ gi ≤ 103) corresponds to the amount of candies earned when buying the i-th and the (i + 1)-th pie."},{"iden":"output","content":"Output a single integer indicating the maximum total amount of candies that Joaozao and Nicoleta can earn."},{"iden":"examples","content":"Input4 6 1 312 3 41 3 2 2 4 11 2 4 8 16Output14Input4 10 3 31 2 32 3 41 2 3 4 3 1 2 4 3 11 1 5 5 2 2 1 5 1Output18"},{"iden":"note","content":"In 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.In 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ K \\in \\mathbb{Z} $ be the number of pie types.  \nLet $ N \\in \\mathbb{Z} $ be the number of pies in the row.  \nLet $ A, B \\in \\mathbb{Z} $ be the sizes of Joaozao’s and Nicoleta’s preference lists, respectively.  \n\nLet $ J \\subseteq \\{1, \\dots, K\\} $ be the set of pie types preferred by Joaozao.  \nLet $ N \\subseteq \\{1, \\dots, K\\} $ be the set of pie types preferred by Nicoleta.  \n\nLet $ P = (p_1, p_2, \\dots, p_N) $ be the sequence of pie types in the row, where $ p_i \\in \\{1, \\dots, K\\} $.  \nLet $ G = (g_1, g_2, \\dots, g_{N-1}) $ be the sequence of candies earned for consecutive pairs, where $ g_i $ is earned if pies at positions $ i $ and $ i+1 $ are bought by the same person.  \n\nLet $ x_i \\in \\{0,1\\} $ be a binary variable:  \n- $ x_i = 1 $ if Joaozao buys pie $ i $,  \n- $ x_i = 0 $ if Nicoleta buys pie $ i $.  \n\n**Constraints**  \n1. For each pie type $ t \\in \\{1, \\dots, K\\} $, all pies of type $ t $ must be assigned to the same person:  \n   $$\n   \\forall i,j \\in \\{1,\\dots,N\\}, \\quad p_i = p_j \\implies x_i = x_j\n   $$  \n2. Joaozao may only buy pies of types in $ J $:  \n   $$\n   \\forall i \\in \\{1,\\dots,N\\}, \\quad p_i \\notin J \\implies x_i = 0\n   $$  \n3. Nicoleta may only buy pies of types in $ N $:  \n   $$\n   \\forall i \\in \\{1,\\dots,N\\}, \\quad p_i \\notin N \\implies x_i = 1\n   $$  \n4. Every pie type appears in at least one preference list:  \n   $$\n   J \\cup N = \\{1, \\dots, K\\}\n   $$  \n5. Every pie type appears at least once in $ P $:  \n   $$\n   \\{p_1, \\dots, p_N\\} = \\{1, \\dots, K\\}\n   $$  \n\n**Objective**  \nMaximize the total candies earned:  \n$$\n\\max \\sum_{i=1}^{N-1} g_i \\cdot \\left( x_i \\cdot x_{i+1} + (1 - x_i) \\cdot (1 - x_{i+1}) \\right)\n$$  \nEquivalently:  \n$$\n\\max \\sum_{i=1}^{N-1} g_i \\cdot \\left(1 - |x_i - x_{i+1}|\\right)\n$$","simple_statement":"Joaozao and Nicoleta must buy all N pies in a row. Each pie has a type from 1 to K. Each person only buys pies of types they like. All pies of the same type must be bought by the same person. If two consecutive pies are bought by the same person, they get candies for that pair. Maximize total candies.","has_page_source":false}