I guess there's not much point in reminding you that Nvodsk winters aren't exactly hot. That increased the popularity of the public transport dramatically. The route of bus 62 has exactly n stops (stop 1 goes first on its way and stop n goes last). The stops are positioned on a straight line and their coordinates are 0 = x 1 < x 2 < ... < x n . Each day exactly m people use bus 62 . For each person we know the number of the stop where he gets on the bus and the number of the stop where he gets off the bus. A ticket from stop a to stop b ( a < b ) costs x b - x a rubles. However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments A , C and D , B , or not sell the ticket at all. The conductor and the passenger divide the saved money between themselves equally. The conductor's "untaxed income" is sometimes interrupted by inspections that take place as the bus drives on some segment of the route located between two consecutive stops. The inspector fines the conductor by c rubles for each passenger who doesn't have the ticket for this route's segment. You know the coordinated of all stops x i ; the numbers of stops where the i -th passenger gets on and off, a i and b i ( a i < b i ); the fine c ; and also p i — the probability of inspection on segment between the i -th and the i + 1 -th stop. The conductor asked you to help him make a plan of selling tickets that maximizes the mathematical expectation of his profit. The first line contains three integers n , m and c ( 2 ≤ n ≤ 150 000 , 1 ≤ m ≤ 300 000 , 1 ≤ c ≤ 10 000 ). The next line contains n integers x i ( 0 ≤ x i ≤ 10 9 , x 1 = 0 , x i < x i + 1 ) — the coordinates of the stops on the bus's route. The third line contains n - 1 integer p i ( 0 ≤ p i ≤ 100 ) — the probability of inspection in percents on the segment between stop i and stop i + 1 . Then follow m lines that describe the bus'