+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، توسط یک مدیرِ منابعِ انسانیِ فروشگاهِ زنجیره‌ایِ ناشی‌تر، مسئولیت داده‌ شده است تا نیاز‌های فروشگاه را از کارخانه‌ها خریداری کند. او باید $m$ جنس را خریداری کند. اجناس را از ۱ تا $m$ شماره‌گذاری میکنیم. $n$ کارخانه وجود دارند(که آنها را از ۱ تا $n$ شماره‌گذاری می‌کنیم.) که هر کدام تمام این $m$ کالا را دارند اما قیمت هایشان برای هر کدام متفاوت است. قیمت کارخانه‌ی $i$ برای جنس $j$، $a_{i,j}$ است. به پروفسور باقر یک پرایدوانت داده‌ شده‌است تا با آنها اجناس را خریداری کند. او الان در فروشگاه است. هر کارخانه تا فروشگاه به اندازه ای فاصله دارد که هزینه بنزین رفت و برگشت $d_i$ است. حالا پروفسور(به علت ناشی بودن) از شما می‌خواهد که به او بگویید که کمینه‌ی هزینه برای خرید این اجناس چقدر است. فقط به این نکته دقت داشته باشید که وقتی پروفسور از فروشگاه به یک کارخانه می‌رود و اجناسی را از آنجا خریداری می‌کند،‌ برای اینکه قاطی نکند که هر جنس را از کدام کارخانه خریده‌است، بلافاصله به فروشگاه برمی‌گردد و اجناس را تحویل می‌دهد و سپس به دنبال اجناس دیگر می‌رود. # ورودی سطر اول ورودی شامل دو عدد $n$ و $m$ است که به ترتیب نمایانگر تعداد کارخانه‌ها و تعداد اجناس است. سپس در $i$امین سطر از هریک از $n$ سطر بعدی: ابتدا $d_i$ آمده‌است که نمایانگر هزینه‌ی بنزین رفت و برگشت از فروشگاه به کارخانه‌ی $i$ ام است. بعد از آن $m$ عدد آمده است که عدد $j$ ام، $a_{i,j}$، نمایانگر قیمت کارخانه‌ی $i$ ام برای جنس $j$ ام است. $$ 1 \le n \le 100 $$ $$ 1 \le m \le 16 $$ $$ 1 \le d_i,a_{i,j} \le 1\ 000\ 000 $$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که نمایانگر کمینه‌ی هزینه برای خرید این $m$ جنس است. # مثال ## ورودی نمونه ۱ ``` 2 2 1 1 1 5 5 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 3 4 5 7 3 7 9 2 1 20 3 2 8 1 20 1 1 ``` ## خروجی نمونه ۲ ``` 16 ``` توضیح: در نمونه‌ی اول پروفسور به کارخانه‌ی اول رفته و تمام اجناس را خریداری می‌کند و برمی‌گردد.در نمونه‌ی دوم: او ابتدا به کارخانه‌ی دوم رفته و اجناس شماره‌ی یک،سه و چهار را خریداری ‌می‌کند و سپس به فروشگاه رفته، اجناس را تحویل می‌دهد(تا اینجا $8$ واحد هزینه داده‌است.) و بعد برای خرید جنس شماره‌ی دو به کارخانه‌ی اول رفته و آن را خریداری می‌کند و به فروشگاه برمی‌گردد(برای بدست‌آوردن جنس دوم هم $8$ واحد پول هزینه می‌کند که در مجموع می‌شود $16$).