해변 도시 timer 1s memory 1024MB

평창은 바다를 향해 나열된 n 개의 언덕으로 이루어진 작은 해변 도시다. 모든 언덕은 다른 위치에 있는데, i번째 언덕은 바다로부터 x_i 미터 떨어져 있다.

각 언덕의 정상에는 스케이트장이 있다. 모든 스케이트장은 매일 동시에 오픈하지만 동일한 시간에 닫지 않는다. i번째 언덕의 스케이트장은 t_i 분 동안 운영한다.

강남이와 강북이는 평창에 와서 m 일 동안 머물 예정이며, 이 도시에서 매일 스케이트를 즐길 계획이다.

둘은 각 날의 시작에 i번째 날에는 a_i 미터만큼 바다에서 떨어진 위치에 있으며, 그들의 스케이팅 모험은 스케이트장이 오픈되는 동일한 시간에 시작된다.

스케이트장에 도달하려면 걸어서 이동해야 하며, 1분에 1미터의 속도로 이동할 수 있다. 그들은 왼쪽이나 오른쪽으로 이동할 수 있다. 언덕이 있는 위치에서는 언덕을 오를 수 있고 그 위에있는 스케이트장에 도달할 수도 있다. 언덕을 오를 때 추가 시간을 소비하지 않는다. 정상에 도달하면 원하는 만큼 또는 스케이트장이 닫힐 때까지 스케이트를 탈 수 있다. 내려갈 때는 올라갈 때만큼 쉽지 않다. 최근에 비가 왔고 지면이 미끄럽기 때문에 i번째 언덕에서 내려오는 데는 s_i 분이 걸린다. 언덕에서 내려오면 다음 스케이트장으로 계속 걸어갈 수 있다.

1번 예제는 다음과 같다.

강남이와 강북이는 시작 지점인 위치 1에 있다. 그들은 언덕 위에있는 위치 3의 스케이트장으로 이동하여 5분 동안 스케이트를 타고 내려온다. 그런 다음 언덕에서 내려온 후(0분), 위치 6의 스케이트장으로 이동하여 1분 동안 스케이트를 탄다. 총, 그들은 5 + 1 = 6분 동안 스케이트를 탄다.

강남이와 강북이는 하루에 여러 개의 스케이트장을 방문할 수 있다면 각 날에 얼마나 많은 시간 동안 스케이트를 탈 수 있는지 궁금하다.

참고: 강남이와 강북이가 하루의 시작에 언덕과 동일한 위치에 있다면 언덕의 아래쪽에 있으므로 스케이트를 타기 위해서는 언덕을 올라가야 한다.