{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the same length land each item i has length li\u003cl. We look for a minimal number of bins q such that\n\n•each bin contains at most 2 items,\n•each item is packed in one of the q bins,\n•the sum of the lengths of the items packed in a bin does not exceed l.\n\nYou are requested, given the integer values n,l,l1, . . . ,ln, to compute the optimal number of bins q.\n\n一组n个一维物品必须装在相同的箱子里。所有仓的长度完全相同,每个物品i的长度为l il。我们寻找一个最小数量的料仓q,使其为\n\n-每个垃圾箱最多容纳两件物品。\n-每件物品都装在一个q箱中。\n-仓内物品的长度之和不超过l。\n\n请你在给定整数n,l,l1,...,ln的情况下,计算出最佳的仓数q。...,ln,计算最佳的仓数q。"}},{"title":"输入内容","value":{"format":"PLAIN","content":"The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.\n\nThe first line of the input file contains the number of itemsn(1\u003c\u003dn\u003c\u003d10^5). The second line contains one integer that corresponds to the bin length l\u003c\u003d10000. We then have n lines containing one integer value that represents the length of the items.\n\n输入的开头是一个正整数,它本身的一行表示后面的案例数,每个案例数如下所述。这一行后面是空行,连续两个输入之间也有空行。\n\n输入文件的第一行包含项数n(1\u003c\u003dn\u003c\u003d10^5)。第二行包含一个整数,对应于bin长度l\u003c\u003d10000。然后,我们有n行包含一个整数值,代表项目的长度。"}},{"title":"輸出結果","value":{"format":"PLAIN","content":"For each test case, your program has to write the minimal number of bins required to pack all items.The outputs of two consecutive cases will be separated by a blank line.\n\nNote:The sample instance and an optimal solution is shown in the figure below. Items are numbered from 1 to 10 according to the input order.\n\n对于每个测试用例,你的程序必须写出包装所有物品所需的最小箱数,两个连续用例的输出将用空行隔开。\n\n注:下图为示例和最佳解决方案。根据输入顺序,物品的编号从1到10。\n"}},{"title":"Sample Input","value":{"format":"PLAIN","content":"1\n10\n80\n70\n15\n30\n35\n10\n80\n20\n35\n10\n30"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"6"}}]}