Under construction

Still being built. Things may change

Double Radars

Time limit1sMemory limit2048 MB

Summary
Pick a start house and move at speed v around a circle of k houses to collect the most coin value without meeting either of two bouncing radars.
Level

Hard8 of 10

Topics
Simulation, Math, Two pointers
Solved
No attempts yet

Problem

Ali recently found a treasure and has arranged the coins from the treasure around a circle. There are kk houses around the circle with equal distances. Houses are numbered 11 through kk consecutively in the clockwise direction. The treasure contains nn coins, where the iith coin (for 1≤i≤n1 \le i \le n) has the value wiw_i and is located at the house xix_i. To protect the treasure, Ali has installed two radars stationed at the center of the circle, monitoring its circumference. Radar ii (for i∈{1,2}i \in \{1, 2\}) starts by monitoring house rir_i and moves 1vi\frac{1}{v_i} houses per minute. More intuitively, every viv_i minutes, Radar ii goes one house forward. Initially, the first radar moves clockwise, and the second radar moves counterclockwise. Whenever the two radars meet, they both reverse their directions. Note that this can happen in the area between two adjacent houses. Gholi, who wants to steal as many coins as possible, plans to start at an arbitrary house on the circle and move at most 1v\frac{1}{v} houses per minute in either direction (clockwise or counterclockwise). He starts moving at time zero. He can reverse his direction anytime or stay still for a while. If Gholi crosses paths with one of the radars at any moment, he is caught and sent to jail. He cannot steal a coin if this happens at a house. Help Gholi maximize the total value of the coins he can steal before being detected by the radars.

Input

The first line contains three integers, nn (1≤n≤1051 \le n \le 10^5) the number of coins, kk (1≤k≤1091 \le k \le 10^9) the number of houses around the circle, and vv (1≤v≤1041 \le v \le 10^4) the speed of Gholi. The second line contains the starting monitoring house r1r_1 and speed v1v_1 of the first radar (1≤r1≤k1 \le r_1 \le k, 1≤v1≤1041 \le v_1 \le 10^4). The third line contains the starting monitoring house r2r_2 and speed v2v_2 of the second radar (1≤r2≤k1 \le r_2 \le k, 1≤v2≤1041 \le v_2 \le 10^4). It is guaranteed that r1≠r2r_1 \ne r_2. The fourth line contains nn distinct integers x1,x2,…,xnx_1, x_2, \dots, x_n, the houses where the coins are located (1≤xi≤k1 \le x_i \le k). The fifth line contains nn integers w1,w2,…,wnw_1, w_2, \dots, w_n, the value of each coin (1≤wi≤1091 \le w_i \le 10^9).

Output

Output the maximum total value of coins Gholi can steal before being detected by the radars.

Examples1

  1. Example 1

    Input
    3 5 1
    1 2
    2 3
    1 2 4
    1 2 4
    
    Expected output
    6