디미고의 학생들은 광덕산을 정말 좋아한다. 등산을 좋아하는 M명의 학생들은 원하는 코스를 정해 광덕산을 오르기로 했다.

광덕산에는 N개의 지점이 있고, 각 지점의 고유한 높이 h가 존재한다. 또한, 광덕산에 있는 지점들은 N−1개의 등산로로 연결되며, 임의의 두 지점 사이를 등산로를 통해 오고 갈 수 있다. i번 지점에서 인접한 j번 지점으로 이동할 때 오르막길이라면 A×|h_i−h_j|, 내리막길이라면 B×|h_i−h_j| 만큼 체력을 소모한다. 즉, i에서 j로 이동할 때,

\begin{cases} A×|h_j−h_i| & \text{if} h_i<h_j \\ B×|h_j−h_i| & \text{if} h_i≥h_j \end{cases}

만큼 체력을 소모한다. 광덕산에는 신묘한 힘이 숨겨져 있기 때문에 값이 음수라면 절댓값만큼의 체력을 회복한다.

목적지에 안전하게 도착하려면 이동 중 체력이 0 이상으로 유지되어야 하며, 도착하는 시점에도 체력이 0 이상이여야 한다. M명의 학생들이 초기 체력 c_i로 a_i에서 출발해 b_i까지 이동할 때, 도착할 수 있다면 도착 시점에서의 체력 최댓값을 출력하고, 도착할 수 없다면 -1을 출력하는 프로그램을 작성하시오.

#8671 upload 17 done 6 how_to_reg 6

광덕산 등산 timer 2s memory 1024MB

#8671

광덕산 등산 2s 1024MB