책 구매하기

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

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

서점은 책을 한 권씩만 택배로 보낸다. 택배비는 서점과 사람 사이의 거리, 회원 등급 등 여러 요인에 따라 정해진다. 서점 $i$가 사람 $j$에게 책 한 권을 보내는 배송비는 $C_{ij}$원이다.

모든 서점과 사람 사이의 배송비가 주어질 때, 각 사람이 원하는 만큼 책을 사는 데 드는 배송비 합의 최솟값을 구하는 프로그램을 작성하시오.

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

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

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

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

$A_1 + A_2 + \dots + A_N$은 $B_1 + B_2 + \dots + B_M$과 같다.

첫째 줄에 배송비 합의 최솟값을 출력한다.

첫 번째 예제에서 서점 1이 사람 3에게 4권, 사람 2에게 1권을 보내고, 서점 2가 사람 1, 사람 2, 사람 4에게 한 권씩 보내고, 서점 3이 사람 1에게 2권, 서점 4가 사람 4에게 한 권을 보내면 배송비의 합은 30이다.