경로
시간 제한1초메모리 제한512 MB
출발 시각과 도착 시각이 정해진 기차들을 이용해 1번 역에서 n번 역까지 이동할 때, 대기 시간에 대한 이차 비용과 최종 도착 시각의 합을 최소로 하는 경로를 구한다.
문제
바이틀랜드의 기차역에는 n개의 역과 m개의 기차가 있다. 각 기차 i는 p_i 시각에 역 x_i에서 출발해 q_i 시각에 역 y_i에 도착한다. 기차 i는 p_i 시각에만 탈 수 있고 q_i 시각에만 내릴 수 있다.
케빈은 역 1에서 출발해 기차를 타고 역 n으로 간다. 목적지에 도착하기 위해 여러 번 갈아탈 수 있다. 구체적으로, y_u = x_v이고 q_u ≤ p_v이면 기차 u에서 기차 v로 갈아탈 수 있다. 이때 케빈은 p_v − q_u만큼 기다린 뒤 p_v 시각에 기차 v를 탄다.
케빈의 불행도를 W라고 하자.
케빈이 갈아타는 과정에서 t만큼 기다릴 때마다 W는 At2 + Bt + C만큼 증가한다 (A, B, C는 주어진 상수다). 특히 시각 0부터 첫 기차를 타는 순간까지의 과정도 갈아타는 것으로 간주하므로, 이때의 대기 시간도 고려해야 한다.
또한 케빈이 시각 z에 역 n에 도착하면 W는 z만큼 증가한다.
케빈의 불행도 W를 최소화하라. 역 n에 도착할 수 있는 계획이 적어도 하나 존재한다.
입력
첫 번째 줄에는 정수 n, m, A, B, C가 주어진다.
다음 m개의 줄에는 각각 x_i, y_i, p_i, q_i가 주어지며, 기차 i의 정보를 나타낸다.
출력
W의 최솟값을 한 줄에 정수로 출력한다.
제한
모든 테스트 케이스는 2 ≤ n ≤ 105, 1 ≤ m ≤ 2×105, 0 ≤ A ≤ 10, 0 ≤ B, C ≤ 106, 1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 0 ≤ p_i < q_i ≤ 103을 만족한다.