0414. Учить или не учить?

Input file name:	exam.in
Output file name:	exam.out
Time limit:	3 s
Memory limit:	256 megabytes

Подходил к концу очередной семестр. До начала сессии осталось всего N дней. Сдавать нужно M экзаменов, а Святослав еще даже не начинал готовиться. Святослав точно знает, что если он начинает готовиться к экзамену i, то ему нужно непрерывно готовиться k_i дней, иначе подготовка пройдет впустую. Для каждого дня он знает величину A_i,j: сколько единиц профита он наберёт по экзамену i если в день j начнёт к нему готовиться и будет непрерывно учить k_i дней. Тщательно осмыслив ситуацию Святослав понял, что нет смысла тщательно готовиться ко всем предметам. Поэтому он решил просто максимизировать суммарную величину профита по всем экзаменам. Святослав не умеет делать несколько дел одновременно, поэтому в один день он не может готовиться более чем к одному экзамену. Если он считает подготовку в какой-либо день бесполезной, то он может лечь спать, и проспать весь день. Святослав считает, что повторение пройденного материала никогда не повредит, поэтому он может готовиться к одному экзамену несколько раз и профит всё равно будет повышаться. Если подготовка к экзамену не будет завершена в течение оставшегося времени, то он её не начинает. Теперь Святослав хочет узнать, какой максимальный профит он может получить за N дней подготовки.

Формат входного файла

В первой строке входного файла содержатся два числа N – количество дней на подготовку и M количество предметов, по которым Святослав может сдавать экзамен. N *M ≤ 10⁶. Во второй строке содержатся M чисел k_i – количество дней, которые необходимы на подготовку к экзамену i. 1 ≤ k_i ≤ 10⁶. Далее идут M строк каждая из которых содержит N чисел A_i,j – величина профита, если в день j Святослав будет готовиться к экзамену i. 0 ≤ A_i,j ≤ 10⁶.

Формат выходного файла

Выведите величину максимального достижимого профита.

Пример:

exam.in	exam.out
4 2 2 3 1 1 1 10 9 5 5 5	9
5 3 1 2 3 0 0 0 0 1 0 2 2 2 2 1 4 4 5 6	5

Discuss       Submit a solution



Printable version