9405번 - Array Game 다국어

There is a single-player game played on a one-dimensional infinite-from-both-ends array containing integers, + signs and - signs. In each turn, the player can move all integers one cell to the left or one cell to the right (signs remain fixed).

The player’s initial score is 0; when an integer I moves into a cell containing the sign S (+ or -), the integer is removed from the array and the score is increased by S × I.

The player can stop the game anytime he/she wants.

Below you can see the initial and the following states of the array, after two right moves are made.

Your task is to find the maximum possible score one can get from a given initial array.

There are multiple test cases in the input. The first line of each test case starts with N (1 ≤ N ≤ 100), the number of integers, followed by N_p (1 ≤ N_p ≤ 100), the number of + signs and N_m (1 ≤ N_m ≤ 100), the number of - signs. Each of the next N lines contains two integers p_i (−300 ≤ p_i ≤ 300), the position and v_i (−9 ≤ v_i ≤ 9), the value of the i^th integer. The following line contains N_p integers indicating the positions of the + signs. The following line contains N_m integers indicating the positions of the - signs. The positions are all between −300 and 300, and no two elements (integers and signs) are initially placed at the same position. The input terminates with a line containing “0 0 0”.

For each test case write a single line containing the maximum possible score.