N + 1 층으로 구성된 던전이 있으며 던전에는 M 명의 플레이어가 있다. 던전의 계층에는 입구에서 가까운 순서로 1 층부터 N+1 층까지의 번호가 붙어 있다. 또한 플레이어는 1에서 M까지 번호가 매겨져 있다.

던전의 한 계층에서 다음 계층으로 진행하려면 체력이 필요하다. 플레이어는 i 층 (1 ≤ i ≤ N)에서 i + 1 층으로 진행할 때 체력을 A_i 소비한다.

또한 이 던전은 일방통행이라 계층 간의 이동은 i 층 (1 ≤ i ≤ N)에서 i + 1 층으로의 이동만 가능하다.

각 층에는 하나의 회복 분수가 있다. i 층 (1 ≤ i ≤ N)에 있는 회복 분수에서 플레이어는 B_i 장의 동전을 소비하여 체력을 1 회복시킬 수 있다.

회복 분수는 동전이 있는 한 여러 번 사용할 수 있다. 그러나 플레이어의 체력에는 상한이 있으며, 회복 분수를 사용해도 체력이 그 상한을 초과하지는 않는다.

플레이어 j (1 ≤ j ≤ M)는 현재 S_j 계층에 있다. 현재 체력은 0이고 체력의 상한은 U_j입니다. 플레이어 j는 체력을 0보다 작게하지 않고 제 T_j 층까지 진행하려고 한다. 그러기 위해서는 몇 장의 동전이 필요할지 알아보자.

던전의 정보와 각 플레이어의 정보가 주어졌을 때, 각 플레이어가 체력을 0 미만으로 하지 않고 목표의 계층까지 진행할 수 있는지 판정해, 가능한 경우에는 필요한 코인의 매수의 최소치를 출력하는 프로그램을 작성하라.

던전 3 timer 4s memory 512MB

던전 3 4s 512MB