지하철에서 만날 역

문제

한 지하철 노선에는 1번부터 N번까지의 역이 번호 순서대로 놓여 있다. 이 노선에서 세 사람이 만나 공동 안내 활동을 준비하려 한다. 세 사람은 동시에 출발하며, 각자 출발한 역에서 선택한 모임 역까지 이동한다. 각 사람의 이동 시간은 아래에 정한 계산 규칙을 따른다. j번째 사람의 출발 역은 A_j이고 이동 계수는 V_j다. 이 사람이 x번 역까지 이동하는 데 걸리는 시간은 |x-A_j|를 V_j로 나눈 값을 올림한 정수 분이다. 여기서 |x-A_j|는 두 역 번호 차이의 절댓값이며, 올림은 나눈 값 이상인 가장 작은 정수를 뜻한다. 출발 역과 모임 역이 같다면 이동 시간은 0분이다. 환승이나 열차 대기 시간은 따로 더하지 않는다. 역마다 안내 활동에 필요한 준비 시간이 다르다. x번 역의 기록 P_x가 0 이상이면 그 역에서 모일 수 있고, 세 사람이 모두 도착한 뒤 P_x분 동안 준비해야 한다. 먼저 도착한 사람은 마지막 사람이 올 때까지 기다린다. 따라서 활동을 시작할 때까지의 시간은 세 사람의 이동 시간 중 가장 큰 값에 그 역의 준비 시간을 더한 값이다. 준비를 이동과 동시에 진행하거나 일부 사람만 도착한 상태에서 시작할 수는 없다. P_x가 -1인 역은 안내 공간을 사용할 수 없어 모임 장소로 선택할 수 없다. 다만 그 역에서 출발하거나 이동 중에 지나가는 것은 가능하다. 준비 시간이 0인 역은 사용할 수 있으며, 모두 도착하는 즉시 활동을 시작한다. 세 사람의 출발 역이 서로 같아도 된다. 활동을 가장 빨리 시작할 수 있는 역을 찾는다. 가장 짧은 시간이 같은 역이 여러 개라면 번호가 가장 작은 역을 선택한다. 선택한 역 번호와 출발 후 활동 시작까지 걸리는 시간을 출력한다. 모든 역의 안내 공간을 사용할 수 없다면 역이나 시간을 선택하지 않고 -1 하나만 출력한다.

입력

첫째 줄에 역의 수 N이 주어진다.
다음 3개 줄의 j번째 줄에 j번째 사람의 출발 역 A_j와 이동 계수 V_j가 주어진다.
마지막 줄에 P_1, P_2, ..., P_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 100,000, 1 ≤ A_j ≤ N, 1 ≤ V_j ≤ 100,000이다. 각 P_x는 -1 또는 0 이상 9 이하의 정수다.

출력

선택할 수 있는 역이 있다면 선택한 역 번호와 활동 시작까지 걸리는 정수 분을 공백으로 구분하여 출력한다. 최적 시간이 같으면 가장 작은 역 번호를 출력한다. 선택할 수 있는 역이 없다면 -1 하나만 출력한다.

5
1 1
5 1
3 2
0 0 2 0 0

2 3

3
1 2
2 1
3 2
-1 -1 -1

-1

1
1 7
1 1
1 9
4

1 4

출처: Devin.KR 자체 제작