Multiplication Table (Python)

Question

Given a multiplication board n * m, each cell has a value of x^2 + y^2 Print the k-th smallest number in that board Input:

• 1st line: n

• 2nd line: m

• 3rd line: k Output:

• The k-th number in that board when sorted

Example:
Input:
2
3
4
Output:
8

Explain: 2 * 3 board:
| 2 | 5 | 10 |
| 5 | 8 | 13 |
Cell (1, 1) = 1**2 + 1**2 = 2
Cell (1, 2) = 1**2 + 2**2 = 5
Cell (1, 3) = 1**2 + 3**2 = 10
Cell (2, 1) = 2**2 + 1**2 = 5
Cell (2, 2) = 2**2 + 2**2 = 8
Cell (2, 3) = 2**2 + 3**2 = 13
When the list is sorted, it result in this: 2, 5, 5, 8, 10, 13 The 4th number is 8

I have try doing this way, but it is too slow. The time limit is 500ms, 0 < a,b,c < 10^9

def kth_smallest_number(n, m, k):     
    values = []      
    for x in range(1, n + 1):         
        for y in range(1, m + 1):             
            values.append(x**2 + y**2)      
    values.sort()     
    return values[k - 1]