cho.sh눈길 부츠
부츠가 쌓인 배낭에서 눈 깊이와 보폭 제한을 고려해 1번 타일에서 N번 타일까지 이동할 때 버려야 하는 부츠 쌍의 최소 개수를 구한다.
보통7동적 계획법배열완전 탐색구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제
농장에 겨울이 왔고 눈이 쌓였다. 농가에서 헛간까지 이어지는 길에는 타일 N개가 1번부터 N번까지 놓여 있고, i번 타일에는 눈이 fi피트만큼 쌓여 있다.
농부 존은 1번 타일에서 출발해 젖소를 깨우러 N번 타일까지 가야 한다. 1번 타일은 농가 지붕 아래에, N번 타일은 헛간 지붕 아래에 있어서 두 타일에는 눈이 없다. 나머지 타일을 밟으려면 부츠를 신어야 한다.
방한 배낭에는 부츠 B켤레가 1번부터 B번까지 들어 있다. 어떤 부츠는 더 튼튼하고 어떤 부츠는 더 날쌔다. i번 부츠를 신으면 깊이가 최대 si피트인 눈까지 밟을 수 있고, 한 걸음에 최대 di칸까지 앞으로 갈 수 있다.
부츠는 차곡차곡 쌓여 있어서 맨 위 한 켤레에만 손이 닿는다. 존은 언제든지 맨 위 부츠를 신을 수 있고, 이때 신고 있던 부츠는 버린다. 맨 위 부츠를 신지 않고 그대로 버려서 그 아래 부츠를 꺼낼 수도 있다.
부츠는 타일 위에 서 있을 때만 갈아 신는다. 그 타일에 눈이 f피트 쌓여 있다면 벗는 부츠와 새로 신는 부츠 모두 깊이 f피트 이상을 견뎌야 한다. 한 번도 신지 않고 버리는 부츠는 이 조건을 지키지 않아도 된다.
처음에 존은 부츠를 신고 있지 않다. 헛간에 도착하려면 부츠를 최소 몇 켤레 버려야 하는지 구하시오.
입력
첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다 (2≤N,B≤250).
둘째 줄에 정수 N개가 공백으로 구분되어 주어진다. i번째 정수는 i번 타일에 쌓인 눈의 깊이 fi이다 (0≤fi≤109). f1=fN=0임이 보장된다.
다음 B개 줄에는 각각 정수 두 개가 공백으로 구분되어 주어진다. i+2번째 줄의 첫 번째 정수는 i번 부츠가 밟을 수 있는 눈의 최대 깊이 si이고, 두 번째 정수는 i번 부츠의 최대 보폭 di이다 (0≤si≤109, 1≤di≤N−1).
부츠는 배낭 위쪽부터 아래쪽 순서로 주어지므로 1번 부츠가 맨 위에 있다.
출력
버려야 하는 부츠의 최소 켤레 수를 정수 하나로 출력한다. 헛간까지 갈 수 있음이 보장된다.