Inspecionando o Emaranhamento

No laboratório do Instituto de Física Quântica, uma equipe de cientistas está conduzindo um novo experimento. A ideia é reconstruir a evolução de um conjunto de partículas emaranhadas ao longo do tempo. O problema é que o experimento não pode ser observado diretamente.

Por isso o laboratório possui uma rede de $N$ sensores quânticos distribuídos no espaço. Os sensores detectam várias propriedades das partículas (spin, polarização, momento angular etc.). No entanto por razões técnicas e energéticas, um mesmo sensor não pode ser ativado por um tempo muito curto (para evitar ruído) e nem permanecer ativo por muito tempo (para evitar o superaquecimento).

O experimento vai durar $T$ segundos. Para que não seja gasta energia à toa e que toda a informação seja coletada, em cada um dos segundos exatamente um dos sensores deve estar ligado coletando informação e nenhum sensor deve permanecer ligado após o termino do experimento.

Cada sensor $i$ no tempo $j$ fornece uma pontuação de confiabilidade $c(i, j)$, refletindo a qualidade da medição naquele instante. O desafio da equipe é selecionar quais sensores ativar ao longo do experimento, garantindo que após um sensor ser acionado ele deve ficar ativo por pelo menos L segundos e no máximo U segundos. Além disso um sensor pode ser utilizado diversas vezes durante o experimento, desde que o tempo para permanecer ativo seja respeitado.

A confiabilidade final do experimento é igual a soma da confiabilidade dos sensores escolhidos a cada segundo durante o teste. O objetivo da equipe é escolher os sensores de forma a maximizar a confiabilidade da reconstrução do estado quântico. Como os físicos estão muito ocupados estudando outros assuntos quânticos, eles enviaram este problema para os times da Fase Zero da Maratona SBC de Programação resolver.

A primeira linha contém dois inteiros $N$ $(1 ≤ N ≤ 5 · 10^3 )$ e $T$ $(1 ≤ T ≤ 100)$ representando respectivamente a quantidade de sensores e o tempo do experimento.

A seguir $N$ linhas, cada uma contendo $T$ inteiros sendo que na $i$-ésima linha o $j$-ésimo inteiro será $c(i, j)$ $(1 ≤ c(i, j) ≤ 5 · 10^7 )$.

A última linha contém dois inteiros $L$ e $U$ $(1 ≤ L ≤ U ≤ T )$ representando o mínimo e o máximo de tempo que cada sensor pode ficar ativo.

Seu programa deve produzir uma única linha com um inteiro representando a maior confiabilidade possível. Caso não tenho solução para as restrições dadas, imprima -1.