JOI 国将举行美术展,在美术展中将展出来自全国各地的各种美术品。
现在有 件候选美术品,编号为 至 。每件艺术品有描述其尺寸与价值的两个整数,第 件艺术品的尺寸为 ,其价值为 。
美术展至少有一件美术品被选中并展示,并且举办美术展的展览馆足够大,所以展出所有的 件美术品也是可行的。为了符合 JOI 国人民的审美,我们想使得参展的美术品之间的尺寸之差不能太大。并且,我们想使得参展的美术品价值之和尽量大。因此,我们决定按照以下方式选定参展的美术品:
在参展美术品中,令 为所选美术品中最大的尺寸, 为所选美术品中最小的尺寸。令 为所有参展美术品的总价值之和。给出候选美术品的数量以及其尺寸与价值,求 的最大值。