시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB796532.830%

문제

동혁건설에서는 이번에 새로운 건물을 짓게 되었다. 건물을 만들기 위해서는 짧은 길이의 강철 파이프가 N개 필요하다. 마침 공사 때 사용하고 남은 긴 길이의 파이프가 M개 있어서 이를 먼저 사용한 뒤 필요한 파이프를 추가 주문하기로 하였다. 동혁건설에서는 가급적이면 적은 개수의 파이프를 추가 주문하려 한다. 즉, 주어진 강철 파이프를 잘라서 최대한 많은 개수의 필요한 파이프를 만들어 내려 한다.

작은 길이의 파이프를 만들기 위해서는 긴 길이의 파이프를 자르면 된다. 자르는 과정에서 파이프의 길이에 손실이 있을 수도 있지만, 문제에서는 이를 무시해도 좋다. 또한, 파이프를 자를 때에는 여러 번 자를 수도 있다.

입력

첫째 줄에 M(1 ≤ M ≤ 50)이 주어진다. 다음 줄에는 M개의 긴 강철 파이프의 길이가 주어진다. 각각의 길이는 100,000을 넘지 않는 양의 정수이다. 다음 줄에는 N(1 ≤ N ≤ 1023)이 주어진다. 다음 줄에는 만들고자 하는 파이프의 길이를 나타내는 정수가 N개 주어진다. 이 길이는 128 이하의 자연수이다.

출력

첫째 줄에 만들 수 있는 필요한 파이프의 최대 개수를 출력한다.

예제 입력 1

4
30 40 50 25
10
15 16 17 18 19 20 21 25 24 30

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjI0MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWM3NzRcdWQ1MDQgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWQ2MDFcdWFjNzRcdWMxMjRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNzc0XHViYzg4XHVjNWQwIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjOWQzXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhYzc0XHViYjNjXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjOWU3XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWFjMTVcdWNjYTAgXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIE5cdWFjMWMgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWI5YzhcdWNlNjggXHVhY2Y1XHVjMGFjIFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWFjZTAgXHViMGE4XHVjNzQwIFx1YWUzNCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIE1cdWFjMWMgXHVjNzg4XHVjNWI0XHVjMTFjIFx1Yzc3NFx1Yjk3YyBcdWJhM2NcdWM4MDAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YjRhNCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Y2Q5NFx1YWMwMCBcdWM4ZmNcdWJiMzhcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWIzZDlcdWQ2MDFcdWFjNzRcdWMxMjRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVhYzAwXHVhZTA5XHVjODAxXHVjNzc0XHViYTc0IFx1YzgwMVx1Yzc0MCBcdWFjMWNcdWMyMThcdWM3NTggXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Y2Q5NFx1YWMwMCBcdWM4ZmNcdWJiMzhcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjMTVcdWNjYTAgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Yzc5OFx1Yjc3Y1x1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YjljY1x1YjRlNFx1YzViNCBcdWIwYjRcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTFcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YWUzNCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Yzc5MFx1Yjk3NFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc5MFx1Yjk3NFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzVkMCBcdWMxOTBcdWMyZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM3NzRcdWI5N2MgXHViYjM0XHVjMmRjXHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHVjNzkwXHViOTdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1Yzc5MFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBNKDEgJmxlOyBNICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YWUzNCBcdWFjMTVcdWNjYTAgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgTigxICZsZTsgTiAmbGU7IDEwMjMpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBOXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMjggXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZlbmNlIFJhaWxzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBpcyB0cnlpbmcgdG8gZXJlY3QgYSBmZW5jZSBhcm91bmQgcGFydCBvZiBoaXMgZmllbGQuIEhlIGhhcyBkZWNpZGVkIG9uIHRoZSBzaGFwZSBvZiB0aGUgZmVuY2UgYW5kIGhhcyBldmVuIGFscmVhZHkgaW5zdGFsbGVkIHRoZSBwb3N0cywgYnV0IGhlJiMzOTtzIGhhdmluZyBhIHByb2JsZW0gd2l0aCB0aGUgcmFpbHMuIFRoZSBsb2NhbCBsdW1iZXIgc3RvcmUgaGFzIGRyb3BwZWQgb2ZmIGJvYXJkcyBvZiB2YXJ5aW5nIGxlbmd0aHM7IEZhcm1lciBKb2huIG11c3QgY3JlYXRlIGFzIG1hbnkgb2YgdGhlIHJhaWxzIGhlIG5lZWRzIGZyb20gdGhlIHN1cHBsaWVkIGJvYXJkcy48XC9wPlxyXG5cclxuPHA+T2YgY291cnNlLCBGYXJtZXIgSm9obiBjYW4gY3V0IHRoZSBib2FyZHMsIHNvIGEgOSBmb290IGJvYXJkIGNhbiBiZSBjdXQgaW50byBhIDUgZm9vdCByYWlsIGFuZCBhIDQgZm9vdCByYWlsIChvciB0aHJlZSAzIGZvb3QgcmFpbHMsIGV0Yy4pLiBJZ25vcmUgdGhlIGBrZXJmJiMzOTsgKGRpc3RhbmNlIGxvc3QgZHVyaW5nIHNhd2luZyk7IHByZXN1bWUgdGhhdCBwZXJmZWN0IGN1dHMgY2FuIGJlIG1hZGUuPFwvcD5cclxuXHJcbjxwPlRoZSBsZW5ndGhzIHJlcXVpcmVkIGZvciB0aGUgcmFpbHMgbWlnaHQgb3IgbWlnaHQgbm90IGluY2x1ZGUgZHVwbGljYXRlcyAoZS5nLiwgYSB0aHJlZSBmb290IHJhaWwgYW5kIGFsc28gYW5vdGhlciB0aHJlZSBmb290IHJhaWwgbWlnaHQgYm90aCBiZSByZXF1aXJlZCkuIFRoZXJlIGlzIG5vIG5lZWQgdG8gbWFudWZhY3R1cmUgbW9yZSByYWlscyAob3IgbW9yZSBvZiBhbnkga2luZCBvZiByYWlsKSB0aGFuIGNhbGxlZCBmb3IgdGhlIGxpc3Qgb2YgcmVxdWlyZWQgcmFpbHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk4gKDEgJmx0Oz0gTiAmbHQ7PSA1MCksIHRoZSBudW1iZXIgb2YgYm9hcmRzPFwvbGk+XHJcblx0PGxpPk4gbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgcmVwcmVzZW50cyB0aGUgbGVuZ3RoIG9mIG9uZSBzdXBwbGllZCBib2FyZDxcL2xpPlxyXG5cdDxsaT5SICgxICZsdDs9IFIgJmx0Oz0gMTAyMyksIHRoZSBudW1iZXIgb2YgcmFpbHM8XC9saT5cclxuXHQ8bGk+UiBsaW5lcyBlYWNoIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciAoMSAmbHQ7PSByPHN1Yj5pPFwvc3ViPiAmbHQ7PSAxMjgpIHRoYXQgcmVwcmVzZW50cyB0aGUgbGVuZ3RoIG9mIGEgc2luZ2xlIHJlcXVpcmVkIGZlbmNlIHJhaWw8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD50aGVuIGNhbGN1bGF0ZSBhbmQgcHJpbnQgYXMgYSBzaW5nbGUgaW50ZWdlciBvbiBhIGxpbmUgdGhlIG1heGltdW0gdG90YWwgbnVtYmVyIG9mIGZlbmNlIHJhaWxzIHRoYXQgY2FuIGJlIGN1dCBmcm9tIHRoZSBzdXBwbGllZCBib2FyZHMuIE9mIGNvdXJzZSwgaXQgbWlnaHQgbm90IGJlIHBvc3NpYmxlIHRvIGN1dCBhbGwgdGhlIHBvc3NpYmxlIHJhaWxzIGZyb20gdGhlIGdpdmVuIGJvYXJkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIE48XC9wPlxyXG5cclxuPHA+TiBzdWJzZXF1ZW50IGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSBzdXBwbGllZCBsZW5ndGg8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBSPFwvcD5cclxuXHJcbjxwPlIgc3Vic2VxdWVudCBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgcmVxdWlyZWQgbGVuZ3RoPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgaW50ZWdlciBvbiBhIGxpbmUuIFRoZSBpbnRlZ2VyIGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiByZXF1aXJlZCBmZW5jZSBsZW5ndGhzIHRoYXQgY2FuIGJlIGN1dCBmcm9tIHRoZSBzdXBwbGllZCBmZW5jZSBzZWN0aW9ucy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 1999-2000 Season > The USACO 1999 Spring Open 1번

  • 데이터를 추가한 사람: doju