책 구매하기 3

N명이 같은 책을 사려고 한다. 사람에게는 1번부터 N번까지 번호가 붙어 있고, 사람 $j$가 사려는 책은 $A_j$권이다. 이 책을 파는 온라인 서점은 M곳이고, 서점에도 1번부터 M번까지 번호가 붙어 있다. 서점 $i$에 있는 책은 $B_i$권이다.

이 책을 사려는 사람은 이 N명뿐이고, 서점에 있는 책의 총합과 사람들이 사려는 책의 총합은 같다.

한 사람이 한 서점에서 사는 양에는 제한이 있다. 사람 $j$는 서점 $i$에서 최대 $C_{ij}$권까지 살 수 있다. 온라인 서점은 책을 한 권씩 따로 택배로 보내고, 배송비는 서점과 사람 사이의 거리, 회원 등급 등 여러 조건으로 정해진다. 서점 $i$가 사람 $j$에게 책 한 권을 보내는 데 드는 배송비는 $D_{ij}$원이다.

구매 제한과 배송비가 모두 주어질 때, 책을 최대 몇 권 살 수 있는지, 그리고 그만큼 살 때 배송비 합의 최솟값은 얼마인지 구하는 프로그램을 작성하시오.

첫째 줄에 사람의 수 N과 온라인 서점의 수 M이 주어진다. ($1 \le N, M \le 100$)

둘째 줄에 각 사람이 사려는 책의 수 $A_1, A_2, \dots, A_N$이 주어진다. ($1 \le A_j \le 100$)

셋째 줄에 각 서점에 있는 책의 수 $B_1, B_2, \dots, B_M$이 주어진다. ($1 \le B_i \le 100$)

넷째 줄부터 M개의 줄에 구매 제한이 주어진다. $i$번째 줄의 $j$번째 수는 사람 $j$가 서점 $i$에서 최대 몇 권까지 살 수 있는지를 뜻하는 $C_{ij}$이다. ($0 \le C_{ij} \le 100$)

그 다음 M개의 줄에 배송비가 주어진다. $i$번째 줄의 $j$번째 수는 서점 $i$가 사람 $j$에게 책 한 권을 보내는 데 드는 배송비 $D_{ij}$이다. ($1 \le D_{ij} \le 1000$)

$A_1 + A_2 + \dots + A_N = B_1 + B_2 + \dots + B_M$이 항상 성립한다.

첫째 줄에 살 수 있는 책의 최대 권수를 출력한다.

둘째 줄에 그 권수를 살 때 드는 배송비 합의 최솟값을 출력한다. 한 권도 살 수 없으면 두 줄 모두 0을 출력한다.