題目描述

現在，你是一位高射炮陣地的士兵。接下來，會有 n 輛敵方坦克來襲，第i輛坦克會在第 a_i 秒抵達，它的價值為 b_i。由於彈藥短缺，我們只能有一門高射炮開火。保證高射炮命中率為100%，命中後的摧毀率為100%。但是這門高射炮的換彈速度為 m 秒，意味著任意兩輛被攻擊的坦克的抵達時間都至少要差 m 秒。問能擊毀的坦克的最高價值總和是多少？

輸入格式

第一行輸入兩個整數 n,m，代表坦克數量和高射炮換彈速度 (1<=n<=1000, 1<=m<=10⁹)

第二到 n+1 行，每行輸入兩個整數 a_i, b_i 代表坦克到達的秒數和該坦克的價值。(1<=a_i<=10⁹, 1<=b_i<=10⁹)

輸出格式

輸出一個整數，代表能擊毀的坦克的最大價值總和。

Samples

["3 3\r\n1 1\r\n2 6\r\n3 5","3 3\r\n1 3\r\n2 6\r\n4 4"]

["6","7"]

提示

在第一個範例中，擊毀第二輛坦克即可，這樣價值總和為6。

在第二個範例中，擊毀第一，三輛坦克即可，這樣價值總和為7。

原始資料

• Zero1 題號：a944
• Hydro 題號：Z0944
• Locale：zh_CN
• Display：open