{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003e公元2411年,人类开始在地球以外的行星建立居住点。在第1326号殖民星上,N个居住点分布在一条直线上。为了方便描述,我们设第i个居住点的位置是Xi,其中居住着Yi位居民。随着冬季的到来,一些人口较多的居住点的生态循环系统已经开始超负荷运转。为了顺利度过严冬,殖民星上的居民一致同意通过转移到人口较少的居住点来减轻人口众多的居住点的负荷。\u003c/p\u003e \n \u003cp\u003e遗憾的是,1326殖民星的环境非常恶劣。在冬季到来前,每个居民点的居民最远能迁移到距离不超过R的居民点。1326殖民星的居民希望知道,如何安排迁移才能使完成迁移后人口最多的居民点人口最少?\u003c/p\u003e \n \u003cp\u003e注意有可能存在多个居民点位置相同。\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003e第一行包含一个整数T(1 \u0026lt;\u003d T \u0026lt;\u003d 10),代表测试数据的组数。\u003c/p\u003e \n \u003cp\u003e每组数据的第一行包含2个整数N(1 \u0026lt;\u003d N \u0026lt;\u003d 100000)和R(0 \u0026lt;\u003d R \u0026lt;\u003d 10^9)。\u003c/p\u003e \n \u003cp\u003e以下N行每行包含两个整数,Xi和Yi(0 \u0026lt;\u003d Xi, Yi, \u0026lt;\u003d 10^9)。\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003e\u003cspan\u003e对于每组数据输出迁移后人口最多的居民点人口最少可能的数目。\u003c/span\u003e\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e3 \r\n5 1 \r\n10 80 \r\n20 20 \r\n30 100 \r\n40 30 \r\n50 10 \r\n5 10 \r\n10 80 \r\n20 20 \r\n30 100 \r\n40 30 \r\n50 10 \r\n5 20 \r\n10 80 \r\n50 10 \r\n20 20 \r\n30 100 \r\n40 30 \u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e100 \r\n50 \r\n48\u003c/pre\u003e \n "}}]}