스무디 가게
면접 대비시간 제한1초메모리 제한512 MB
보유한 k개 재료의 양과, 각 재료 사용량과 가격이 정해진 r개 레시피가 주어질 때, 한 레시피만 골라 최대한 많이 만들어 얻을 수 있는 최대 매출을 구한다.
문제
Olivia는 아주 유명하고 수익성 좋은 스무디 가게를 운영한다. 어떤 날이든 그녀는 어떤 스무디 레시피를 내놓든 항상 재고가 떨어질 때까지 판다(즉, 재료가 허락하는 만큼 스무디를 판다). 그래서 일을 단순하게 만들기 위해, 그녀는 하루에 한 종류의 스무디만 만들기로 했다. 이제 그녀는 오늘 가지고 있는 재료와 각 스무디의 판매 가격을 고려해 어떤 레시피를 쓸지 정하는 일을 당신에게 부탁했다.
입력
첫째 줄에 공백으로 구분된 두 정수 와 이 주어진다. 는 Olivia가 스무디에 사용하는 서로 다른 재료의 수이고, 은 그녀가 만드는 서로 다른 레시피의 수이다. , , 이라고 가정해도 된다. 둘째 줄에는 그녀가 현재 가지고 있는 각 재료의 양을 나타내는 개의 정수가 주어진다. 이어서 개의 줄이 주어지며, 각 줄이 레시피 하나를 나타낸다. 각 줄에서 공백으로 구분된 처음 개의 정수는 그 레시피에 들어가는 각 재료의 양을 나타낸다. 그 뒤에 그 레시피의 스무디 한 잔에 대해 받는 가격을 나타내는 정수 하나가 주어진다. 와 을 제외한 모든 값은 이하의 음이 아닌 정수라고 가정해도 된다. 각 레시피는 적어도 하나의 재료를 사용한다.
출력
레시피 하나를 골라 그 레시피를 최대한 많이 만들었을 때 얻을 수 있는 최대 총매출을 출력한다.