Migrated from Lutece 1438 智慧总裁772002

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

772002是一家专门制作咸鱼的公司的总裁，这天772002的公司来了个大客户Xiper，Xiper非常喜欢吃咸鱼，一次向772002订购了许多咸鱼。

772002的咸鱼公司一共有n种咸鱼产品，m个员工，对于第i种咸鱼，Xiper订购了pi条。而且每个员工一次只能加工一条咸鱼，并且不同员工加工同种咸鱼所花的时间可能是不同的。对于第i种咸鱼，第j个员工加工一条所花的时间为tij。在接到尊贵的VIP会员Xiper的订单后，m个员工同时开始制作咸鱼，对于每条咸鱼制做所花费的代价为从一开始生产咸鱼到生产完这条咸鱼时间。

772002是一个智慧的总裁，他肯定会通过合理的安排让生产代价最小，所以772002想知道，最小的生产代价是多少。

Input

第一行两个整数n(1<=n<=40),m(1<=m<=100)。

接下来一行n个整数0<=pi<=800，所有pi的总和不会超过800.

接下来n行，每行m个整数1<=tij<=1000表示第j个人加工一条i种咸鱼所花的时间。

Output

一个整数，所花费的最小代价是多少。

Samples

  3 2 
  3 1 1 
  5 7 
  3 6 
  8 9

  47

Resources

2016 UESTC Training for Graph Theory