ماموریت آرامش
Problem
خدمه کشتی بین سیاره ای سرنیتی کلاس Firefly محموله را به سیارات مختلف منظومه ستاره ای تحویل می دهد. کشتی دارای یک انبار محموله محموله است که از N × سلول های M. هر سلول محفظه بار دارای حداکثر حجمی است که می تواند در خود جای دهد. قرار دادن باری با حجم بیشتر از حداکثر حجم سلول در سلول غیرممکن است. فقط یک بار را می توان در یک سلول قرار داد.
آرامش کاپیتان مالکوم رینولدز از طریق قرار دادن محموله در سلول ها فکر می کند. به او کمک کنید حداکثر مقدار محمولی را که کاپیتان می‌تواند تحویل دهد تعیین کند.
ورودی
خط اول شامل اعداد N و M است (\(1 \leq N, M \leq 40\) ). هر یک از خطوط N زیر حاوی اعداد M است که حداکثر حجم سلول مربوطه را نشان می‌دهد. خط (N+2)ام حاوی عدد K است (\(1 \leq K \leq 2000\)) – مقدار محموله خط (N+3)-امین اعداد K است که i-امین آنها &ndash است; حجم iمین بار. همه جلدها – اعداد طبیعی که از 10 تجاوز نمی کنند9.
حصر
نمایش یک عدد – حداکثر مقدار محموله ای که می توان تحویل داد.
مثال
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
|
4 |
Запрещенные операторы: sort