1440: 정호쌤의 극한의 가성비 하스스톤
메모리제한：256 MB
시간제한：3.000 S
Judge Style：Text Compare
만든사람：
제출：1
통과：1
문제 설명
충남과학고등학교 정보교사이신 박정호 선생님은 하스스톤을 즐겨 하신다. 어느날 하스스톤의 개발사 블리자드에서는 카드뽑기 확률을 높여주는 VIP쿠폰 이벤트를 시작하였고, 돌겜러인 정호쌤은 이 VIP쿠폰의 효과를 이벤트 기간동안 유지하고 싶어한다.
VIP쿠폰에는 유지기간과 가격이 다른 n개 종류가의 쿠폰이 존재하며, 쿠폰은 중복구매가 가능하다.
이벤트 기간 중에는 VIP쿠폰을 절반가격으로 구매할 수 있는 Half DAY가 존재한다.
단, 이미 VIP쿠폰 혜택을 받고 있을 때 VIP쿠폰을 별도 구매할 수 없으며, 쿠폰은 구매 즉시 발동된다.
이벤트 기간이 끝나면 VIP쿠폰의 남은 유지기간과 관계없이 효과가 종료되게 되는데, 정호쌤은 극한의 가성비를 챙기려 하기 때문에 이런 손해를 보는 경우밖에 없을 때에는 아예 이벤트에 참여하지 않으려 한다.
정호쌤을 도와 하스스톤 VIP쿠폰 이벤트에서 극한의 가성비를 챙길 수 있도록 해보자.
[2020년 충남과학고 3학년 임O준 제작]
입력 설명
이벤트 기간 d가 입력된다.(1<=d<=10000)
d일동안 각 날짜가 Half DAY인지 여부를 순서대로 입력된다.(Half DAY이면 1 아니면 0이 입력된다.)
쿠폰의 종류 개수 n개가 입력된다.(1<=100);
각 쿠폰의 유지일수 a와 가격 b가 차례대로 n개 입력된다.
출력 설명
이벤트 기간동안 VIP쿠폰 혜택을 유지할 수 있으면, 그 최저 비용을 출력하고, 아니면 -1을 출력한다.
입력 예시 Copy
10
0 0 0 0 0 1 0 0 0 0
3
10 8
5 5
2 3출력 예시 Copy
7도움
[입력예시2]
0 0 0 1 0 1 1 1 0 0
4
10 8
10 7
5 4
2 3
[출력예시2]
6
0 0 0 1 0 1 1 1 0 0
4
10 8
10 7
5 4
2 3
[출력예시2]
6