Ефект метелика
Є кілька подій, які повинні відбутися. Кожна подія може мати або позитивний, або негативний результат, що впливає на ймовірність результатів наступних подій.
Події відбуваються в порядку, зазначеному у вхідних даних. Для кожної події i є пов'язане з нею ціле базове значення, яке позначимо b[i]. Щоб визначити результат події, ми кидаємо симетричний m-сторонній кубик, сторони якого пронумеровані від 1 до m, і додаємо число, що випало на кубику, до базового значення. Якщо результат строго позитивний, то результат події позитивний. В іншому випадку (включаючи, якщо результат дорівнює нулю), результат негативний. Якщо подія має позитивний результат, ми змінюємо базові значення всіх наступних подій відповідно до списку модифікаторів, пов'язаних з цією подією. Тобто, якщо подія i має позитивний результат, то нове базове значення для події j дорівнює b[j] + p[ij], де p[ij] - модифікатор для події j у разі позитивного результату події i. Якщо результат негативний, ми робимо те ж саме, але з іншим списком модифікаторів; базове значення для події j стає рівним b[j] + q[ij], де q[ij] - відповідний модифікатор.
Ви маєте можливість втрутитися в певну кількість подій. Коли ви втручаєтеся, замість того щоб кидати один кубик, ви кидаєте два і обираєте той результат, який вам більше підходить. Для кожної події ви вирішуєте, чи варто втручатися безпосередньо перед киданням кубика, тобто ви можете використовувати результати попередніх подій, щоб вирішити, втручатися чи ні. Чи можете ви максимізувати ймовірність того, що остання подія матиме позитивний результат?
Вхідні дані
Перший рядок містить три цілі числа n, k і m (1 ≤ k ≤ n ≤ 20, 4 ≤ m ≤ 1000), що описують кількість подій, максимальну кількість втручань і розмір кубика. Далі йдуть 3n рядків, що описують базові значення і модифікатори подій у такому форматі:
Рядок 3i - 1: Одне ціле число
b[i]- базове значення для події i. Базове значення для кожної події за модулем не більше 2000.Рядок 3i: n - i цілих чисел
p[i,i+1], ...,p[in]- модифікатори базових значень для подій від i + 1 до n у разі позитивного результату події i. Кожен модифікатор за модулем не більше 2000.Рядок 3i + 1: n - i цілих чисел
q[i,i+1], ...,q[in]- модифікатори базових значень для подій від i + 1 до n у разі негативного результату події i. Кожен модифікатор за модулем не більше 2000.
Остання подія не має модифікаторів, тому останні два рядки входу порожні.
Вихідні дані
Виведіть єдине число, яке дорівнює максимальній ймовірності отримати позитивний результат для останньої події, з точністю до 6 десяткових знаків.