Депозит#5760

Депозит

2 секунди

256 мегабайтів

Легка

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Приклад 1