This problem is exactly the same as Leetcode378 Kth Smallest Element in a Sorted Matrix, the only difference is this problem give two array while 378 gives a matrix, but they are the same. You can check my previous post for 378 to see how it works.

https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-solution

```
public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
int m = nums1.length, n = nums2.length;
List<int[]> res = new ArrayList<int[]>();
if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res;
for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j]));
for(int i = 0; i < Math.min(k, m *n); i++) {
Tuple t = pq.poll();
res.add(new int[]{nums1[t.x], nums2[t.y]});
if(t.x == m - 1) continue;
pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y]));
}
return res;
}
}
class Tuple implements Comparable<Tuple> {
int x, y, val;
public Tuple (int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo (Tuple that) {
return this.val - that.val;
}
}
```