• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...

«میسیکس» دوست و همراه قدیمی مِسِریکس بود که به علت بزرگ بودن و رد نشدن عقایدش از فیلتر‌‌های مِسِریکس دوستی‌شان ادامه پیدا نکرد. به اعتقاد میسیکس علت بحران محیط زیست خود ما آدم‌ها هستیم و باید نابود شویم.

یک شب میسیکس به آزمایشگاه تحقیقات سلاح‌های شیمیایی حمله می‌کند تا تعدادی سم کشنده برای قتل عام بشریت بدزدد. او از قبل متوجه شده‌است که $k$ نوع سم کشنده در این آزمایشگاه وجود دارد و با $i$-امین سم می‌شود $p_i$ نفر را کشت. همچنین به ازای هر سم $i$ و $j$ می‌دانیم اگر به لوله‌ی آزمایش حاوی سم $j$، سم $i$ را اضافه کنیم سم $a_{i,j}$ بدست می‌آید. توجه کنید که $a_{i,j}$ ممکن است با $a_{j,i}$ متفاوت باشد.

میسیکس در آزمایشگاه یک میز می‌بیند که روی آن $n$ لوله‌ی آزمایش حاوی سم قرار دارد. $i$-امین لوله دارای سم $t_i$ است. وقت او اندک است و می‌خواهد تعدادی از سم‌ها را بدزدد که با آن‌ها بتواند در مجموع بیشترین تعداد آدم را بکشد. چون او از قبل جدول تبدیل مواد را دارد می‌تواند در مراحلی هر بار یکی از دو کار زیر را انجام دهد:

• دو لوله آزمایش که کنار هم هستند (یعنی در میان آن‌ها لوله‌ای نیست) را بردارد و چپی را درون راستی بریزد و لوله چپی را دور بیندازد. یعنی اگر در لوله چپ سم $x$ باشد و در لوله راست سم $y$ باشد با ریختن چپی در راستی به سم $a_{x,y}$ می‌رسیم.
• یکی از لوله‌ها را بردارد و در ساکش بگذارد.

مِسِریکس متوجه حمله میسیکس به آزمایشگاه شده‌است و می‌خواهد محاسبه کند سم‌هایی که او دزدیده‌است حداکثر چند نفر را می‌کشند چون این تعداد قطعا پارامتری موثّر در بحران محیط زیست است.

ورودی

در سطر اول ورودی به ترتیب دو عدد $k$ و $n$ آمده‌است.

در سطر دوم $k$ عدد آمده‌است که عدد $i$-ام برابر با $p_i$ است.

در $i$-امین سطر از $k$ سطر بعدی $k$ عدد آمده‌است که عدد $j$-ام برابر با $a_{i,j}$ است.

سپس در سطر آخر $n$ عدد آمده‌است که عدد $i$-ام برابر با $t_i$ است.

$$1 \le k \le 30$$ $$1 \le n \le 85$$ $$0 \le p_i \le 1\ 000\ 000$$ $$1 \le a_{i,j} \le k$$ $$1 \le t_i \le k$$

خروجی

در تنها سطر خروجی حداکثر تعداد نفراتی که میسیکس با دستکاری و دزدیدن سم‌ها می‌تواند بکشد را چاپ کنید.

مثال

ورودی نمونه ۱

4 9
2 3 6 5
1 3 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 4 2 2 2 2

خروجی نمونه ۱

29

با توجه به جدول تبدیل و هزینه‌ها تنها به‌صرفه است که ۱ و ۲ را ترکیب کنیم و به ۳ برسیم. برای رسیدن به جواب بهینه ابتدا سم ۴ را می‌دزدیم و سپس چهار بار لوله سم ۱ را درون لوله سم ۲ می‌ریزد و به سم ۳ می‌رسد و آن را درون کیفش می‌گذارد. در نهایت او یک سم ۴ دارد و چهار سم ۳ و جمع تعداد نفراتی که این سموم می‌کشند ۲۹ می‌شود.