Банкiвська справа
Молодий ломбардець Гуччо Бальйонi (герой серiї творiв французького письменника Морiса Дрюона) часто виконував таємнi доручення сучасних йому можновладцiв Францiї, Анґлiї та Італiї. Не маючи можливостi протягом трьох рокiв безпосередньо самому займатися справами, вiн вирiшив отримати зиск, вклавши грошi у справи паризьких банкiрiв. Виявилося, що розмiр винагороди (% зиску) рiзний у рiзних банкiрiв. Звичайно, чим бiльшу суму вiн дасть банкiру, тим бiльше отримає через 3 роки. І не менше, нiж дав банкiру. Але в кожного банкiра % зиску рiзний для рiзних сум. Нажаль, за розрахунками Гуччо, йому нiколи не отримати бiльше ніж 1000 лiврiв (середньовiчних французьких монет).
Домоможіть молодому ломбардцю отримати найбiльшi статки.
Вхідні дані
Перший рядок мiстить кiлькiсть лiврiв m (1 ≤ m ≤ 100), яку молодий Гуччо може використати для збагачення та кiлькiсть паризьких банкiрiв n (1 ≤ n ≤ 100).
Для j в межах вiд 1 до m (j + 1)-ий рядок мiстить послiдовнiсть n натуральних чисел. k-ий член цiєї послiдовностi -це кiлькiсть монет, яку отримає Гуччо через три роки вiд k-го банкiра, вiддавши йому j монет перед вiд'їздом.
Вихідні дані
Перший рядок має мiстити найбiльшу кiлькiсть лiврiв, яку може мати молодий ломбардець через 3 роки, використавши m лiврiв належним чином.
Другий рядок має мiстити послiдовнiсть n невiд'ємних цiлих чисел. k-ий член цiєї послiдовностi - це кiлькiсть лiврiв, яку має дати Гуччо k-му банкiру, щоб отримати максимальний зиск вiд своїх капiталовкладень (потрiбно подати хоча б один з варiантiв розподiлу).