Consideremos un viejo reproductor de casets, el cual solamente trabaja con los botones de reproducir y retroceder. Tu tienes un caset el cual siempre se encuentra al comienzo de la cinta, entonces cuando tu quieres escuchar una determinada canción s, tu tienes que presionar el botón de reproducir y escuchar todas las canciones que se encuentran antes que termine s. Después de eso cuando terminas de escuchar la canción s tu retrocedes la cinta del caset al principio nuevamente.

Tu tienes N canciones todas tiene la misma duración D. Tu también conoces que una canción i la escuchas con una determinada frecuencia fi (Para una instancia, si f1=6 y f2=3, entonces tu escuchas la canción 1 dos veces mas que la canción 2). Asumamos que tienes las N canciones en un caset. Tu tarea consiste en escoger el orden en que tiene que estar las canciones grabadas en el caset para minimizar el tiempo de espera al momento de escuchar una canción deceada.

La entrada consiste en varios casos de prueba. Cada caso de prueba contiene dos números D y N,(1<= N <= 10⁵, 1<=D<=10⁴) seguido por n números que son las frecuencias de las canciones,(0<=ni<=10⁴).

Por cada caso de prueba, imprimir con cuatro dígitos después del punto decimal la esperanza del tiempo de espera mínimo posible para escuchar las canciones.