눈 장화

농장에 겨울이 왔고, 그것은 곧 눈을 의미한다! 농가에서 헛간으로 가는 길에는 \(N\)개의 타일이 있으며, 편의상 \(1 \dots N\)으로 번호가 매겨져 있고, 타일 \(i\)는 \(f_i\)피트 깊이의 눈으로 덮여 있다.

농부 존은 타일 \(1\)에서 출발하여 소들을 깨우기 위해 타일 \(N\)에 도달해야 한다. 타일 \(1\)은 농가 지붕이, 타일 \(N\)은 헛간 지붕이 가려 주고 있으므로 이 두 타일에는 눈이 없다. 하지만 다른 타일들을 밟으려면 농부 존은 장화를 신어야 한다!

악천후용 배낭 안에 농부 존은 \(1 \dots B\)로 번호가 매겨진 \(B\)켤레의 장화를 가지고 있다. 어떤 켤레는 다른 것보다 더 튼튼하고, 어떤 켤레는 더 민첩하다. 구체적으로, \(i\)번째 켤레는 농부 존이 깊이 최대 \(s_i\)피트의 눈을 밟을 수 있게 해 주고, 한 걸음에 최대 \(d_i\)만큼 앞으로 나아갈 수 있게 해 준다.

안타깝게도 장화들은 농부 존이 어느 시점에든 맨 위의 켤레에만 접근할 수 있는 방식으로 포장되어 있다. 그래서 어느 시점에든 농부 존은 맨 위의 장화를 신거나(이전 장화는 버린다), 맨 위의 장화를 버릴 수 있다(그러면 새로운 장화에 접근할 수 있게 된다).

농부 존은 타일 위에 서 있을 때만 장화를 갈아 신을 수 있다. 그 타일에 \(f\)피트의 눈이 있다면, 벗는 장화와 신는 장화 모두 적어도 \(f\)피트의 눈을 견딜 수 있어야 한다. 신지 않고 그냥 버리는 중간의 장화들은 이 제한을 만족할 필요가 없다.

농부 존이 낭비를 최소화할 수 있도록, 헛간에 도달하기 위해 버려야 하는 장화의 최소 켤레 수를 구해 주자. 농부 존은 처음에 아무 장화도 신고 있지 않다고 가정해도 된다.

출제자: Brian Dean, Dhruv Rohatgi

출제자: Brian Dean, Dhruv Rohatgi

첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(B\)가 주어진다 (\(2 \leq N,B \leq 250\)).

둘째 줄에 공백으로 구분된 정수 \(N\)개가 주어진다. \(i\)번째 정수는 타일 \(i\) 위의 눈 깊이 \(f_i\)이다 (\(0 \leq f_i \leq 10^9\)). \(f_1 = f_N = 0\)임이 보장된다.

다음 \(B\)개의 줄에는 각각 공백으로 구분된 정수 두 개가 주어진다. \(i+2\)번째 줄의 첫 번째 정수는 \(i\)번째 켤레로 밟을 수 있는 눈의 최대 깊이 \(s_i\)이다. \(i+2\)번째 줄의 두 번째 정수는 \(i\)번째 켤레의 최대 보폭 \(d_i\)이다. \(0 \leq s_i \leq 10^9\)이고 \(1 \leq d_i \leq N-1\)임이 보장된다.

장화는 위에서 아래 순서로 주어지므로, \(1\)번째 켤레가 농부 존의 배낭 맨 위에 있는 켤레이고, 이하 같은 식이다.

농부 존이 버려야 하는 장화의 최소 켤레 수를 나타내는 정수 하나를 출력한다. 농부 존이 헛간까지 갈 수 있음이 보장된다.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Silver