There are ants living on a stick of length units. The initial position of the -th ant is units away from the left side of the stick. Some of the ants are facing left at the beginning, while the others are facing right. All ants will move at a speed of 1 unit per second in the direction they're facing. When two ants meet face to face at the same point, both of them will turn around instantly and move on.
There are also two obstacles on the sides of the stick, one located on the leftmost and the other on the rightmost. When an ant runs into one of them, it will also turn around instantly and move on. However, the obstacles aren't indestructible. The left one will break after hits, while the right one will break for hits. After an ant passes through a broken obstacle it will fall from the stick. Note that the number of hits is calculated independently for each obstacle, and that the ant which breaks the obstacle will also turn around and will not fall immediately.
In how many seconds will all ants fall from the stick?
输入格式
There is only one test case in each test file.
The first line of the input contains three integers , and (, ) indicating the number of ants, the number of hits to break the left obstacle and the number of hits to break the right obstacle.
The second line contains integers (, ) indicating the initial position of ants.
The third line contains integers (). If then the -th ant is facing left initially, otherwise it is facing right.
输出格式
Output one line containing one integer indicating the number of seconds for all ants to fall from the stick.
