Problema A - Empacotadores

A Covilhã é conhecida não só pela serra da Estrela e pela sua universidade (a Universidade de Beira Interior), mas também pela sua indústria de robôs empacotadores, um dos expoentes da qual é a empresa Ubirobô.

A Ubirobô fabrica actualmente o robô empacotador Mach1. Este robô aceita artigos de diversos volumes e coloca-os cada um numa caixa. Os artigos vêm num tapete, um a seguir ao outro, e em cada momento há uma sequência de caixas disponíveis, não necessariamente iguais, numa linha de empacotamento. O que o robô faz é pegar em cada artigo que surge no tapete, e, deslocando-se sobre as caixas que estão na linha de empacotamento, coloca-o dentro da primeira caixa onde o artigo cabe, isto é, cujo espaço livre é suficiente para conter o artigo. Se não for possível metê-lo em nenhuma das caixas (porque não cabe em nenhuma) o robô coloca o artigo numa zona especial da qual depois será retirado para processamento manual, o que fica muito caro.

Durante o processamento, quando uma caixa fica a conter 10 artigos ou quando o espaço livre se torna inferior a 5% do seu volume, a caixa é retirada automaticamente e é substituída por uma caixa nova retirada de uma fila de caixas vazias.

Vai agora entrar em produção um novo robô, o Mach2. Este é bem mais sofisticado: tem memória e é programável. Você é o engenheiro de software da Ubirobô e cabe-lhe escrever o programa que vai controlar esta maravilha tecnológica. Em primeira aproximação, temos dois algoritmos: Best Fit e Worst Fit. No Best Fit, cada artigo é colocado na caixa com menor espaço livre de entre aquelas que têm espaço livre suficiente. Em caso de empate, o robô escolherá a caixa com posição mais baixa. No Worst Fit, cada artigo é colocado na caixa com maior espaço livre (desde que caiba, claro). Em caso de empate, prefere-se outra vez a posição mais baixa. Tirando a escolha da caixa a colocar, o Mach2 funciona de modo análogo ao Mach1, ou seja, uma caixa é retirada quando fica a conter 10 artigos ou quando o seu espaço livre é inferior a 5% do seu volume.

A sua tarefa é decidir qual dos dois algoritmos é melhor. Para isso, deve escrever um programa para simular o comportamento dos dois algoritmos e, já agora, também o funcionamento do robô Mach1.

Em cada simulação, o seu programa processará uma descrição das caixas e dos artigos e escreverá, no final, para cada caso, o número de artigos empacotados e o número de caixas usadas. As caixas usadas são aquelas que no final do processamento não ficaram vazias.

O Problema

Input

A primeira linha contém o número de caixas, N, 1 ≤ N ≤ 100.

A segunda linha contém o número de posições da linha de empacotamento, K, 1 ≤ K ≤ 100. Seguem-se N linhas, cada uma com um número real representando a capacidade de uma caixa. As caixas são colocadas na linha de empacotamento pela ordem por que vêm indicadas no input.

Segue-se uma linha que contém o número de artigos, M, 0 &le M &le 1000. Seguem-se M linhas, cada uma com um número real representando o volume de cada artigo.

Output

Exemplo de Input 1

3
2
10.0
8.0
9.0
6
2.0
5.7
2.3
7
1.1
6.6

Exemplo de Output 1

6 3
6 3
4 2

Exemplo de Input 2

3
3
10
9
8
5
2
7
10
2
6

Exemplo de Output 2

4 2
5 3
4 3