Есть несколько событий, которые должны произойти. Каждое событие имеет либо положительный результат, либо отрицательный, и они влияют на вероятность результатов последующих событий.

События происходят в порядке, указанном на входе. Для каждого события i имеется связанное с ним целочисленное базовое значение, которое мы обозначим bi. Чтобы решить исход события, мы бросим симметричный m-сторонний кубик, стороны которого обозначены от 1 до m, и добавим число, выпавшее на кубике, к базовому значению. Если результат строго положительный, то результат положительный. В противном случае (в том числе, если результат равен нулю), возникает отрицательный результат. Если происходит положительный результат, мы изменяем базовые значения всех последующих событий в соответствии со списком модификаторов, связанных с событием. То есть если результат события i положительный, то новое базовое значение для события j равно bj + pij, где pij - модификатор для события j в случае положительного исхода события i. Если исход отрицательный, мы делаем то же самое но только с другим списком модификаторов; базовое значение для события j становится равным bj + qij, где qij ассоциированный модификатор.

У вас есть право вмешаться в определенное количество событий. Когда вы вмешиваетесь, то вместо того чтобы бросать один кубик, Вы бросаете два, после чего выбираете тот результат, который предпочитаете. Для каждого события Вы решаете, следует ли вмешаться непосредственно перед бросанием кубика, то есть Вы можете использовать результаты предыдущих событий, чтобы решить, вмешиваться или нет. Можете ли Вы максимизировать вероятность окончательного события, имеющего положительный результат?

Входные данные

Первая строка содержит три целых числа n, k и m (1 ≤ k ≤ n ≤ 20, 4 ≤ m ≤ 1000), описывающих количество событий, наибольшее возможное количество вмешательств и размер кубика. Далее идут 3n строк, описывающие базовые значения и модификаторы событий в следующем формате:

• Строка 3i - 1: Одно целое число bi - базовое значение для события i. Базовое значение для каждого события по модулю не более 2000.
• Строка 3i: n - i целых чисел pi,i+1, ..., pin - модификаторы базовых значений для событий от i + 1 до n в случае положительного исхода события i. Каждый модификатор по модулю не более 2000.
• Строка 3i + 1: n - i целых чисел qi,i+1, ..., qin - модификаторы базовых значений для событий от i + 1 до n в случае негативного исхода события i. Каждый модификатор по модулю не более 2000.

Последнее событие не имеет модификаторов, и, таким образом, последние две входные строки пусты.

Выходные данные

Выведите единственное число, равное максимальной вероятности иметь положительный результат для заключительного мероприятия, с точностью 6 десятичных знаков.