Before entering a closed olympiad in informatics, there are participants waiting for entrance, numbered from to . It is known that every minute, one participant will be invited into the competition hall in the order of their numbers. In one minute, the first participant will enter the hall, in two minutes the second participant will enter, and so on. Thus, the -th participant will enter the hall minutes after the start of the entrance process.
Each participant has a certain level of anxiety before the olympiad. The anxiety level of each participant is given by some integer (which may be negative). Before the start of the entrance process, the anxiety level of participant is equal to . Every minute, the anxiety level of the participant will change by . Therefore, after minutes from the start of the entrance process, the anxiety level of participant will be equal to .
Alexander is an experienced psychologist who decided to calm the participants waiting to enter the olympiad. To do this, Alexander talks to the participants and calms them down. He can talk to each participant no more than once. After talking to Alexander, the anxiety level of the participant becomes and does not change afterward. The of Alexander's work with participant is considered to be the level of anxiety of the participant at the moment of communication with Alexander. Thus, if Alexander talks to participant after minutes from the start of the entrance process into the olympiad, the will be equal to . Note that if the anxiety level of the participant was negative, then the will also be negative.
Alexander will work with the participants in the order of their numbers. However, Alexander does not have to talk to all participants, meaning it is possible that he will not communicate with the last participants in line. Note that Alexander will talk to each participant no more than once and this must happen before the participant enters the competition hall. At the same time, Alexander can communicate with several participants at once every minute. More formally, Alexander's work process can be described as follows:
Alexander has a predetermined plan for working with the participants. The work plan is given by a sequence of integers , , , . For each , if , then by the time the first participants are allowed into the competition hall (after minutes from the start of the entrance process), Alexander must talk to the first participants and no one else. In this case, it is also guaranteed that . If , it means that there are no restrictions on the number of participants with whom Alexander must work after minutes from the start of the entrance process.
More formally, if , then:
Help Alexander determine what the maximum possible of his work with the participants can be while satisfying all the constraints. It is guaranteed that the answer always exists.
The first line contains a single integer () --- the number of participants waiting in line to enter the competition hall of the olympiad.
The next lines contain two integers and (, ) --- the anxiety parameters of the -th participant.
The following line contains integers , , , ( or ) --- the description of the work plan for Alexander.
It is guaranteed that for any pair , it holds that , if and .
Output a single number --- the maximum possible of Alexander's work.
It can be shown that Alexander will always be able to perform his work while adhering to all additional constraints and the work plan.
4
3 -6
4 -10
-7 -3
-3 6
3 3 -1 -1
15
4
-6 -1
-5 14
0 10
-30 2
2 3 -1 -1
-1
4
-6 -1
-5 14
0 10
-30 2
-1 -1 -1 -1
23
In the first test example, it is optimal to choose and . Then the will be:
In the second test example, it is optimal to choose and . Then the will be:
In the third test example, it is optimal to choose and . Then the will be:
The tests for this problem consist of fourteen groups. Points for each group are awarded only if all tests of the group and all tests of some previous groups are passed. Note that passing the tests from the statement is not required for some groups. means that the results of testing your solution on this group will only be available after the end of the competition. The final score for each group is equal to the maximum score obtained for that group of tests across all submissions.
| Group | Points | Additional constraints | < | Necessary groups | Comment | |
|---|---|---|---|---|---|---|
| -- | -- | -- | -- | Tests from the statement. | ||
| ^ | -- | -- | ^ | |||
| -- | ||||||
| ^ | -- | -- | ^ | |||
| -- | -- | |||||
| ^ | -- | ^ | ||||
| -- | -- | |||||
| ^ | -- | ^ | ||||
| -- | -- | |||||
| ^ | -- | ^ | ||||
| -- | -- | Number no more than 10 | ||||
| ^ | -- | ^ | ||||
| -- | , , , , , | Offline testing | ||||
| ^ | -- | -- | ^ | |||