물약 구매
면접 대비시간 제한3초메모리 제한1024 MB
각 포션의 가격과 한 포션을 살 때 다른 포션의 가격이 얼마나 깎이는지가 주어질 때, 모든 포션을 사는 데 드는 최소 비용을 구합니다.
문제
준겸이는 모험가이다. 모험을 떠나려면 철저한 사전 준비를 갖춰야 한다.
준겸이는 모험을 떠나기 전에 종류의 물약을 모두 사려고 한다. 물약 상점에 들른 준겸이는 각 물약에 1번부터 번까지 번호가 매겨져 있다는 것을 알았다. 그런데 상점에서 오늘 특별한 이벤트를 하고 있었다. 특정 물약을 사면 다른 물약 몇 개가 할인된다는 것이다.
번째 물약의 원래 가격은 동전 개이다. 번째 물약을 사면 다른 물약 종류의 가격이 내려간다.
할인은 중첩된다. 예를 들어 1번 물약을 사면 3번 물약이 동전 1개만큼 할인되고, 2번 물약을 사면 3번 물약이 동전 2개만큼 할인된다고 하자. 두 물약을 모두 산 뒤에 3번 물약을 사면 동전 3개만큼 할인을 받는다. 다만 물약 가격은 0 이하로 내려가지 않는다. 예를 들어 원래 가격이 동전 5개인 물약이 동전 4개를 넘는 만큼 할인되더라도 가격은 동전 1개가 된다.
준겸이는 신이 나서 물약을 사려다가, 물약을 사는 순서가 중요하다는 사실을 깨달았다. 준겸이가 물약을 모두 가장 싸게 샀을 때의 비용을 구하여라.
입력
첫째 줄에 물약의 종류 이 주어진다.
둘째 줄에 물약의 가격 가 공백을 사이에 두고 주어진다 ().
다음 줄부터 물약 할인 정보가 개 주어진다. 번째 할인 정보는 다음과 같다 ().
가 주어진다. 다음 개의 줄에는 물약 번호 와 할인되는 가격 가 주어진다. 이는 번 물약을 사고 나면 물약 가 동전 개만큼 할인된다는 뜻이다.
출력
첫째 줄에 물약을 가장 싸게 샀을 때 필요한 동전의 개수를 출력한다.
제한
- 각 에 대해, 모든 는 서로 다르고 이다