Nikola is a passionate collector of albums with images of football players. He and his friends compete with each other in a game they invented based on the albums whose images are currently being collected. The images in that album are divided into teams, each of which has exactly football players. The main rule of the game is that the total number of points a person wins for team is , where is the total number of unique pictures of football players of that team collected by the person. They have also agreed that the array is growing, i.e. having more unique images of football players of a team means having more or equal points.
Nikola would like to win as many points as possible in the game. For each team the amount of unique images Nikola currently owns of that team, , is known.
Ivan is a friend of Nikola who has already collected the entire album twice and when he heard about the game Nikola plays with his friends, he decided to give him any images that Nikola wants. After finding out about this joyful news, Nikola wondered what is the maximal number of points he could have after Ivan gives him images. Too excited for this news, he is not able to count and begs you to answer his question.
In the first line there are integer numbers , and , numbers from the task's text.
In the second line there is an array consisting of non-negative integer numbers .
In the third line there is an array consisting of non-negative integer numbers , amount of points Nikola gets for unique images of a team.
For every between and it holds .
It is also holds that .
In the only line print the answer to Nikola's question.
In test samples totally worth 20% of the points it will hold .
Sample Input 1
4 4 3 4 2 3 1 0 1 3 6 10
Sample Output 1
Explanation for Sample Output 1
Nikola is most likely to ask Ivan to give him an image of the third team and two from the second, so that his score is .
Sample Input 2
4 3 5 1 1 2 3 0 1 2 3
Sample Output 2
Sample Input 3
3 6 2 2 4 1 31 38 48 60 75 91 120
Sample Output 3