Since everything is already in sorted order, python's sort function greatly makes use of this and minimizes the time needed to actually sort (so that sorting is closer to O(n))

```
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
a=[]
for r in matrix:
a.extend(r)
return sorted(a)[k-1]
```