Скоро у Васи день рождения, на который он пригласил $N$ друзей. Для застолья он планирует приготовить $M$ разных салатов. Осталось определиться, сколько ложек какого салата необходимо приготовить.

Вася отлично знает предпочтения своих друзей. А именно, он знает значения $H_{i,j}$ --- количество единиц счастья, которое принесёт одна ложка $j$-го салата $i$-му гостю ($1 \le i \le N$, $1 \le j \le M$). Кроме того, ему известно, что в желудок $i$-го гостя помещается $V_i$ ложек салата.

Наш Вася очень любит своих друзей, поэтому он хочет приготовить столько салатов, чтобы каждый друг был максимально счастлив. Например, если $i$-й гость съест $C_1$ ложек $j$-го салата и $C_2$ ложек $k$-го салата ($C_1 + C_2 \le V_i$), то он получит $C_1 \cdot H_{i,j} + C_2 \cdot H_{i, k}$ единиц счастья.  

С другой стороны, Вася не любит, когда какого-то салата слишком много на столе, а также, когда после застолья остаётся лишняя еда. Поэтому он хочет тщательно рассчитать объем каждого салата. Его цели в порядке приоритета: 
\begin{enumerate}
\item Сделать максимально счастливыми всех его друзей
\item Минимизировать объем самого большого салата на столе
\item Минимизировать суммарный объём приготовленных салатов
\end{enumerate}

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