D - Un tren con dos destinos

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

En un almacén de suministros se tiene un tren listo para partir con todos sus vagones llenos de materias primas. Estas han de ser entregadas en dos fábricas ubicadas en distintos lugares del país. El tren normalmente va con todos los vagones hasta un punto equidistante de ambas fábricas donde deja su carga y luego vuelve al almacén. En ese punto los vagones se dividen en dos conjuntos y dos trenes más pequeños se  los llevan a su destino final. El problema ahora es que al ser más pequeños este par de trenes, entonces es posible que no todos los vagones puedan ser llevados en un viaje a las fábricas desde el punto donde los dejó el primer tren, lo que termina generando una situación incómoda. Es fácil entender que si se deja algún vagón esperando por un viaje futuro,  entonces se entorpecería el tráfico en ese punto del recorrido y además los vagones pudieran resultar blanco de potenciales ilegalidades.

El objetivo en este problema consiste en escoger la mayor cantidad de vagones para trasladar en el primer tren, de forma tal que sea posible dividirlo en dos conjuntos que puedan ser llevados cada uno por un tren pequeño. Como las dos industrias son de igual importancia los dos conjuntos deben tener la misma cantidad de vagones, aunque tengan peso total distinto (por ejemplo si tienen distintos materiales dentro). Dado que no se tiene mucho tiempo para escoger los vagones al inicio entonces los que se hace es separar uno de los vagones del resto, de esta forma el tren solo se lleva los vagones que están antes del que es separado y el resto se queda en el almacén bien vigilado.

Input

La primera línea contiene dos enteros $n$ $(1 \leq n \leq 50)$ y $W$ $(1 \leq W \leq 5000)$ que representan respectivamente la cantidad de vagones y el mayor peso que puede transportar un tren pequeño. La siguiente línea tiene $n$ enteros separados por un espacio, donde cada uno indica el peso de un vagón. El valor de cada peso es un entero menor o igual a $700$ y se dan en el orden que aparecen inicialmente al salir y antes de la separación que se menciona al final del problema.

Output

La salida es una única línea con la mayor cantidad de vagones que es posible transportar hacia las fábricas, respetando las exigencias planteadas.

Sample test(s)

Input
5 10 6 6 5 3 3
Output
2