Comentário por Murilo Maeda
Nesse problema há duas dificuldades principais: o tamanho grande da matriz, então não podemos nem percorrê-la nem mantê-la em uma matriz, e a forma desorganizada que os números aparecem na matriz, não há um padrão que nos permita concluir coisas sobre a posição e organização de números na matriz.
Para resolver o primeiro problema, basta simplesmente não mantermos a matriz. Vamos manter somente os vetores $$x$$ e $$y$$ e quando precisarmos de um valor, só somamos os valores necessários de $$x$$ e $$y$$.
Agora, vamos resolver o segundo problema.
Note que, como queremos encontrar os $$K$$ menores números, a posição deles na matriz não importa. Por isso, podemos ordenar os vetores $$x$$ e $$y$$, do menor para o maior e formar a matriz $$M$$ na qual $$M_{ij} = x[i] + y[j]$$ . Agora, temos duas propriedades dessa matriz: em uma mesma linha, se a percorrermos de $$1$$ a $$N$$, os valores estarão dispostos em ordem não decrescente. O mesmo ocorre quando percorremos uma coluna de $$1$$ a $$N$$.
A partir disso, vamos analizar o que acontece quando queremos saber quantos valores menores ou iguais a um determinado valor $$c$$ estão na matriz $$M$$. Note que, se encontrarmos em uma determinada linha $$l$$ o índice $$k$$ de modo que o valor $$M_{lk}$$ é o maior valor maior ou igual a $$c$$ na linha $$l$$, nas linhas com índice menor que $$l$$, o maior valor maior ou igual a $$c$$ vai estar em um índice maior ou igual a $$k$$, já que os valores em uma coluna e em uma linha estão em ordem não decrescente. Por isso, para um determinado número $$c$$, para descobrir quantos valores menores ou iguais a ele estão na matriz $$M$$, podemos simplesmente fazer o seguinte: passamos pela linha n e pegamos $$k_n$$ e o somamos no número de valores menores ou iguais a $$c$$. Para uma linha $$l$$: a percorremos a partir do índice $$k_{l+1}$$ enquanto os valores forem menores ou iguais a $$c$$. Paramos no índice $$k_{l}$$ e somamos $$k_l$$ no número de valores menores ou iguais a $$c$$.
Com isso, podemos calcular em $$O(n)$$ quantos valores são menores ou iguais a $$c$$ na matrisz $$M$$. Então, basta fazermos uma busca binária na resposta, tentando encontrar o valor que queremos. Fazemos isso chutando o número da resposta, checando quantos valores são menores ou iguais a ele em $$M$$ e em seguida comparando esse resultado com $$k$$.
Segue o código para maior esclarecimento:
https://gist.github.com/murilomaeda/4abaa1c81232045cc9e0787d4d76d4d6