Депозит

За багато років трудового стажу Василь Іванович заробив $k$ рублів. Тепер Василь Іванович пішов на пенсію і хоче покласти ці гроші на депозит на найближчі $m$ років. У його рідному місті працює $n$ банків. Якщо у Василя Івановича у банку з номером $i$ на протязі $j$-го року на рахунку лежать гроші, то у кінці року їх кількість на цьому рахунку збільшиться на $p_{i,j}$ процентів.

На початку кожного року Василь Іванович може, якщо хоче, перерозподілити грощі, які лежать на рахунках у банках. Процес перерозподілу грошей відбувається у чотири етапи. Спочатку він вибирає множину банків які приймають участь у перерозподілі. Потім Василь Іванович знімає усі гроші, які лежать у цих банках. Після цього він платить комісію кожному з вибраних банків. У кінці у кожен з вибраних банків він кладе на рахунок стільки грошей, скільки він хоче, причому сумарно на рахунки Василь Іванович кладе усі гроші, які він зняв. При цьому у множині вибраних банків можуть у тому числі бути банки, де у Василя Івановича не було грошей, або у які він не планує покласти гроші. У банка під номером i комісія становить ai рублів. Якщо у Василя Івановича недостатньо грошей, щоб заплатити комісію, то він віддає усі зняті гроші банкам, які приймали участь у перерозподілі грошей.

На початку першого року Василь Іванович може безкоштовно покласти довільне число рублів на депозити у довільні банки, причому сумарно на депозити він покладе усі свої гроші.

Знайдіть максимальне сумарне число рублів на усіх рахунках Василя Івановича у кінці $m$-го року.

Вхідні дані

У першому рядку міститься натуральне число $t$ — кількість тестів ($1$ ≤ $t$ ≤ $50$).

Опис кожного теста починається з рядка, що містить три цілих числа $n$, $m$ та $k$ — кількість банків, років, та зароблених грошей відповідно ($1$ ≤ $n$ ≤ $10000$, $1$ ≤ $m$ ≤ $20$, $1$ ≤ $k$ ≤ $10^9$). У наступному рядку міститься $n$ цілих чисел, де $i$-е число рівне $a_i$ — комісія $i$-го банку ($1$ ≤ $a_i$ ≤ $10^9$). У кожному з наступних $n$ рядків міститься по $m$ цілих чисел. У $i$-му рядку $j$-е число рівне $p_{i,j}$ — процент додаткових грошей, отримуваних Василем Івановичем у $j$-му році на рахунок у $i$-му банку ($0$ ≤ $p_{i,j}$ ≤ $100$).

Сумарна кількість банків у всіх тестах не перевищує $50000$.

Вихідні дані

Для кожного тесту у окремому рядку виведіть максимальну сумарну кількість грошей на усіх рахунках Василя Івановича у кінці m-го року. Ваша відповідь буде зарахована, якщо її відносна похибка не перевищує $10^{-6}$.

Приклади