도시 I와 도시 O 사이를 이동하는 고속버스가 있다.

버스에는 정수기가 있어, 승객과 운전사가 물을 마실 수 있다.

버스는 0초에 도시 I에서 출발해서, X초에 도시 O에 도착한다.

경로에는 N개의 리필 구역이 있어 정수기에 물을 다시 채울 수 있다.

버스는 i번째 리필 구역(1 ≤ i ≤ N)을 S_i초에 지날 것이다.

시작할 때, 정수기에는 물이 들어있지 않다.

출발 전에 정수기에 물을 채울 수 있다.

또한, 버스가 리필 구역에 있을 때도 정수기에 물을 채울 수 있다.

물의 비용은 버스의 위치에 상관없이 리터당 W원이다.

도시 I에서, M명의 승객이 버스에 탑승한다.

승객은 1번부터 M번까지 번호가 붙여져 있다.

어떤 승객도 도시 I 이외의 곳에서 버스에 탑승하지 않는다.

j번 승객(1 ≤ j ≤ M)은 D_j초부터 시작해서 T초마다 물 1리터를 마셔야 한다.

다른 말로, j번 승객은 D_j + kT(k = 0, 1, 2, ...)초에 물을 마셔야 한다.

1 ≤ Dj < T을 만족하며, 모든 승객에 대하여 T의 값은 동일하다.

승객이 물을 마셔야 할 때 정수기에 물이 들어있지 않다면 승객은 버스에서 내린다.

j번 승객이 도시 O에 도착하기 전에 버스에서 내린다면 C_j원을 환불해 주어야 한다.

운전자 또한 물을 마셔야 한다.

운전자는 0초부터 시작해서 T초마다 물 1리터를 마셔야 한다.

다른 말로, 운전자는 kT(k = 0, 1, 2, ...)초에 물을 마셔야 한다.

운전자가 물을 마셔야 할 때 정수기에 물이 들어있지 않다면 버스의 운행은 멈춘다.

같은 시간에 서로 다른 두 명의 사람이 물을 마시는 일은 없음이 보장된다.

또한, 버스가 도시 O나 리필 구역에 도착하는 순간에 물을 마셔야 하는 사람은 없음이 보장된다.

각 리필 구역에서 정수기에 넣을 물의 양을 조절함으로서 도시 O까지 버스를 운행시키면서, 동시에 물에 대한 비용과 환불 금액의 합을 최소화시키고 싶다.

당신은 어디서 얼만큼 정수기에 물을 넣어야 하는지를 정해야 한다.

버스의 운행 시간, 리필 구역의 정보, 승객과 운전자의 정보가 주어진다.

버스가 도시 O까지 운행할 때 물에 대한 비용과 환불 금액의 합의 최솟값을 구하여라.

Long Distance Coach timer 2s memory 256MB

Long Distance Coach 2s 256MB