问题描述

已知有$\tt n$个物品，每个物品有其对应的重量$\tt w_i$.小明有一个背包，背包由于质量有限，只允许放入$\tt m,m\le 3$个物品(可以不用放满$\tt m$个物品),且物品的重量总和不能超过$\tt W,W\le 1000$,小明想知道背包里最多出现多少种不同的重量。

格式

输入描述

第一行三个整数$\tt n,m,W.$

第二行有$\tt n$个整数，每个数表示物品重量$\tt w_i$

输出描述

一个整数,背包中有多少不同的重量

样例输入

样例输入1

3 2 1000

1 2 3

样例输出1

5

限制

对于$\tt 30\%$的数据,$\tt m=1$.

对于$\tt 60\%$的数据,$\tt m=2$.

对于$\tt 100\%$的数据 $\tt m\le 3,n\le 100,W,w_i\le 1000$

1s, 1024KiB for each test case.