Demy 는 n 개의 보석을 가지고 있다. 각각의 보석은 vi 의 값어치와 wi 의 무게를 가지고 있다.

그녀의 남편이 최근의 금융 위기에 파산을 해서 , 그녀는 가지고 있는 보석의 일부를 팔기로 하였다. 그녀는 k 개의 가장 좋은 보석을 간직하기로 결정 하였다.

즉 , 보석 S = { i1,i2,..,ik }의 값을 다음과 같이 측정하기로 하였다.

Demy 는 이 값이 최대가 되도록 하는 k 개의 보석을 선택하고자 한다.

입력

다음 n 줄에는 각 줄당 vi 와 wi 가 주어진다. (0 ≤ vi ≤ 10^6, 1 ≤ wi ≤ 10^6, vi + wi <= 10^7)

출력

입출력 예

입력

3 2
1 1
1 2
1 3

출력

1 2

출처: Northeastern Europe 2005, Northern Subregion