Depozit

Za uzun illər əmək fəaliyyəti ərzində Viktor Ivanesku $k$ avro qazanıb. İndi o, təqaüdə çıxıb və bu məbləği yaxın $m$ il ərzində depozitə qoymaq istəyir. Onun yaşadığı şəhərdə $n$ bank fəaliyyət göstərir. Əgər Viktor Ivanesku $i$ nömrəli bankda $j$-ci il ərzində pul saxlayırsa, ilin sonunda həmin hesabdakı pulun miqdarı p_{i,j} faiz artacaq.

Hər ilin əvvəlində Viktor Ivanesku banklardakı pullarını yenidən bölüşdürə bilər. Bu proses dörd mərhələdən ibarətdir. Əvvəlcə o, yenidən bölüşdürmədə iştirak edəcək bankları seçir. Sonra həmin banklardan bütün pulları çıxarır. Daha sonra o, seçilmiş hər bir banka komissiya ödəyir. Sonda isə seçilmiş bankların hər birinə istədiyi qədər pul yatırır, lakin ümumilikdə çıxardığı bütün pulları yenidən hesablarına qoyur. Seçilmiş banklar arasında əvvəllər pulu olmayan və ya pul qoymağı planlaşdırmadığı banklar da ola bilər. $i$ nömrəli bankda komissiya a_i avrodur. Əgər Viktor Ivaneskunun komissiyanı ödəmək üçün kifayət qədər pulu yoxdursa, o, çıxardığı bütün pulları yenidən bölüşdürmədə iştirak edən banklara yatırır.

Birinci ilin əvvəlində Viktor Ivanesku istənilən sayda avronu istənilən banklara pulsuz olaraq depozitə qoya bilər, lakin ümumilikdə bütün pullarını depozitlərə yatırmalıdır.

$m$-ci ilin sonunda Viktor Ivaneskunun bütün hesablarında olan maksimum ümumi avro miqdarını tapın.

Giriş məlumatları

Birinci sətirdə təbii ədəd $t$ — testlərin sayı ($1$ ≤ $t$ ≤ $50$) verilir.

Hər bir testin təsviri üç tam ədəd $n$, $m$ və $k$ — bankların, illərin və qazanılmış pulların sayı ilə başlayan sətirdən ibarətdir ($1$ ≤ $n$ ≤ $10000$, $1$ ≤ $m$ ≤ $20$, $1$ ≤ $k$ ≤ 10^9). Növbəti sətirdə $n$ tam ədəd var, burada $i$-ci ədəd a_i — $i$-ci bankın komissiyasıdır ($1$ ≤ a_i ≤ 10^9). Növbəti $n$ sətirdə hər birində $m$ tam ədəd var. $i$-ci sətirdə $j$-ci ədəd p_{i,j} — Viktor Ivaneskunun $j$-ci ildə $i$-ci bankda hesabında aldığı əlavə pulun faizidir ($0$ ≤ p_{i,j} ≤ $100$).

Bütün testlərdəki bankların ümumi sayı $50000$-dən çox deyil.

Çıxış məlumatları

Hər bir test üçün ayrı sətirdə $m$-ci ilin sonunda Viktor Ivaneskunun bütün hesablarında olan maksimum ümumi pul miqdarını çıxarın. Cavabınız qəbul ediləcək, əgər onun nisbi səhvi 10^{−6}-dan çox deyilsə.