題目連結：
題目大意：
第一列給定兩正整數 n 、 S （1 ≦ n ≦ 50 ， 1 ≦ S ≦ 10 ^ 5），代表有 n 隻寵物以及 S 份的星塵砂子。接著有 n 列輸入，每列給定兩非負整數 CP 、 IV （0 ≦ CP ≦ 10 ^ 6 、 0 ≦ IV ≦ 45），並依照給定的順序編號。
根據 IV 區間的不同，寵物的 CP 值成長幅度不同。每一次升級消耗 1000 星塵。一次升級如果 IV 為 0 ～ 29 ，CP 提升 10 ； IV 30 ～ 39 提升 50 ；IV 40 ～ 45 提升 100 。
在盡可能消耗掉所有星塵砂子的狀況下，請找出投資到哪隻編號的寵物最後的 CP 值最高？
範例輸入：