Вы находитесь на дуэльной арене. Вы также владеете \(n\) покемонами. Изначально на арене находится только \(1\)-й покемон.
Каждый покемон имеет \(m\) характеристик. Значение \(j\)-й характеристики у \(i\)-го покемона равно \(a_{i,j}\). Также у каждого покемона есть стоимость его вызова: цена \(i\)-го покемона равна \(c_i\).
Вы хотите добиться того, чтобы на арене находился \(n\)-й покемон. Для этого вы можете выполнять операции двух типов любое количество раз в любом порядке:
- Выбрать три целых числа \(i\), \(j\), \(k\) (\(1 \le i \le n\), \(1 \le j \le m\), \(k > 0\)) и навсегда увеличить \(a_{i,j}\) на \(k\). Стоимость такой операции равна \(k\).
- Выбрать два числа \(i\), \(j\) (\(1 \le i \le n\), \(1 \le j \le m\)) и вызвать \(i\)-го покемона, который бросит вызов текущему покемону на арене по \(j\)-й характеристике. При этом \(i\)-й покемон победит, если \(a_{i,j}\) не меньше, чем \(j\)-я характеристика текущего покемона на арене (иначе он проиграет). После дуэли на арене остаётся только её победитель. Стоимость такой операции равна \(c_i\).
Найдите наименьшую суммарную стоимость операций, необходимых для того, чтобы на арене оказался \(n\)-й покемон.
Примечание
В первом наборе входных данных массив значений характеристик \(1\)-го покемона (который изначально расположен на арене) есть \([2,9,9]\).
На первой операции можно выбрать \(i=3\), \(j=1\), \(k=1\) и увеличить \(a_{3,1}\) на \(1\) навсегда. Теперь массив значений характеристик \(3\)-го покемона станет равен \([2,2,1]\). Стоимость этой операции равна \(k = 1\).
На второй операции можно выбрать \(i=3\), \(j=1\) и вызвать \(3\)-го покемона, который сразится с текущим покемоном на арене по \(1\)-й характеристике. Поскольку \(a_{i,j}=a_{3,1}=2 \ge 2=a_{1,1}\), \(3\)-й покемон победит. Стоимость этой операции равна \(c_3 = 1\).
Таким образом, \(3\)-й покемон находится на арене, а суммарная стоимость операций равна \(2\). Можно показать, что меньше \(2\) ответ получить нельзя.
Во втором наборе входных данных массив значений характеристик \(1\)-го покемона есть \([9,9,9]\).
На первой операции можно выбрать \(i=2\), \(j=3\), \(k=2\) и увеличить \(a_{2,3}\) на \(2\) навсегда. Теперь массив значений характеристик \(2\)-го покемона есть \([6,1,9]\). Стоимость этой операции равна \(k = 2\).
На второй операции можно выбрать \(i=2\), \(j=3\) и вызвать \(2\)-го покемона, который сразится с текущим покемоном на арене по \(3\)-й характеристике. Поскольку \(a_{i,j}=a_{2,3}=9 \ge 9=a_{1,3}\), \(2\)-й покемон победит. Стоимость этой операции равна \(c_2 = 3\).
На третьей операции можно выбрать \(i=3\), \(j=2\) и вызвать \(3\)-го покемона, который сразится с текущим покемоном на арене по \(2\)-й характеристике. Поскольку \(a_{i,j}=a_{1,2}=2 \ge 1=a_{2,2}\), \(3\)-й покемон победит. Стоимость этой операции равна \(c_3 = 1\).
Таким образом, \(3\)-й покемон находится на арене, а суммарная стоимость операций равна \(6\). Можно показать, что меньше \(6\) ответ получить нельзя.