Задача A. Домашние задания ≡

Условие

Петя очень не любит делать домашние задания. Поэтому он просит отличников из своего класса сделать их за него. За это он даёт им шоколадные конфеты. Так как Петин папа работает на шоколадной фабрике, то у Пети всегда много конфет.

Но отличники — капризные ребята. В разные дни они просят разное количество конфет за выполнение домашнего задания. Про каждого отличника в классе Петя знает, сколько конфет придётся ему дать в i-й день учёбы, чтобы тот сделал за него домашнее задание. Кроме того, каждый день делать домашние задания за Петю не согласится ни один отличник, и поэтому про каждого отличника Петя выяснил, какое максимальное количество домашних заданий тот согласится сделать за него подряд.

Требуется написать программу, которая по информации о количестве конфет, которое отличники просят за свои услуги, а также о максимальном количестве дней подряд, которое каждый отличник готов делать домашние задания за Петю, определяет, какое минимальное количество конфет требуется Пете, чтобы все домашние задания были за него сделаны.

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

Первая строка входного файла содержит два числа: n — количество учебных дней, m — количество отличников в классе у Пети.

Вторая строка входного файла содержит m целых чисел a_i (1 ≤ i ≤ m), задающих для каждого отличника максимальное количество заданий подряд, которое он согласен выполнять за Петю (1 ≤ a_i ≤ n).

Следующие m строк содержат по n неотрицательных целых чисел, при этом j-е число i-й строки (c_{i, j}) означает количество конфет, которое Пете придётся отдать i-му отличнику, чтобы он сделал за Петю домашнее задание в j-й день.

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

Ограничения

Примеры тестов

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

9
1 1 2 2 1

Задача B. Разнообразные строки ≡

Условие

Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно один раз. Например, разнообразность строки "INFORMATICS" - 9, поскольку символы "A", "C", "F", "M", "N", "O", "R", "S" и "T" встречаются в ней ровно один раз.

Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких подстрок несколько, то найдите ту, которая минимальна в лексикографическом порядке.

Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:

1. A является началом B;
2. для некоторого числа i первые i символов строки A совпадают с первыми i символами строки B, а i+1-й символ в строке A идет в алфавите раньше i+1-го символа в строке B.

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

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

Ограничения

Примеры тестов

ABBAC

BAC

OLYMP

OLYMP

AAA

A

Задача C. Чёрно-белый поворот ≡

Условие

Чёрно-белое изображение состоит из h строк по w пикселей. Каджый пиксель имеет значение 0 или 1. С целью экономии памяти изображение было сжато следующим образом: для каждой строки сначала записывается значение первого пикселя, затем длины цепочек подряд идущих нулей и единиц. Например, строка 00100001110 будет закодирована последовательностью 0, 2, 1, 4, 3, 1.

Данное сжатое чёрно-белое изображение требуется повернуть на 90 градусов по часовой стрелке, и вывести, используя тот же метод сжатия.

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

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

Ограничения

Примеры тестов

3 3
1 3
1 1 1 1
0 2 1

0 1 2
0 2 1
1 3

2 4
1 2  1 2  0 2  0 2

0 2 2
0 2 2