시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 207 0 0 0.000%

문제

동혁건설에서는 이번에 새로운 건물을 짓게 되었다. 건물을 만들기 위해서는 짧은 길이의 강철 파이프가 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBNKDEmbGU7TSZsZTs1MClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHVhZTM0IFx1YWMxNVx1Y2NhMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IE4oMSZsZTtOJmxlOzEwMjMpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBOXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMjggXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGZW5jZSBSYWlscyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgdHJ5aW5nIHRvIGVyZWN0IGEgZmVuY2UgYXJvdW5kIHBhcnQgb2YgaGlzIGZpZWxkLiBIZSBoYXMgZGVjaWRlZCBvbiB0aGUgc2hhcGUgb2YgdGhlIGZlbmNlIGFuZCBoYXMgZXZlbiBhbHJlYWR5IGluc3RhbGxlZCB0aGUgcG9zdHMsIGJ1dCBoZSYjMzk7cyBoYXZpbmcgYSBwcm9ibGVtIHdpdGggdGhlIHJhaWxzLiBUaGUgbG9jYWwgbHVtYmVyIHN0b3JlIGhhcyBkcm9wcGVkIG9mZiBib2FyZHMgb2YgdmFyeWluZyBsZW5ndGhzOyBGYXJtZXIgSm9obiBtdXN0IGNyZWF0ZSBhcyBtYW55IG9mIHRoZSByYWlscyBoZSBuZWVkcyBmcm9tIHRoZSBzdXBwbGllZCBib2FyZHMuPFwvcD5cclxuXHJcbjxwPk9mIGNvdXJzZSwgRmFybWVyIEpvaG4gY2FuIGN1dCB0aGUgYm9hcmRzLCBzbyBhIDkgZm9vdCBib2FyZCBjYW4gYmUgY3V0IGludG8gYSA1IGZvb3QgcmFpbCBhbmQgYSA0IGZvb3QgcmFpbCAob3IgdGhyZWUgMyBmb290IHJhaWxzLCBldGMuKS4gSWdub3JlIHRoZSBga2VyZiYjMzk7IChkaXN0YW5jZSBsb3N0IGR1cmluZyBzYXdpbmcpOyBwcmVzdW1lIHRoYXQgcGVyZmVjdCBjdXRzIGNhbiBiZSBtYWRlLjxcL3A+XHJcblxyXG48cD5UaGUgbGVuZ3RocyByZXF1aXJlZCBmb3IgdGhlIHJhaWxzIG1pZ2h0IG9yIG1pZ2h0IG5vdCBpbmNsdWRlIGR1cGxpY2F0ZXMgKGUuZy4sIGEgdGhyZWUgZm9vdCByYWlsIGFuZCBhbHNvIGFub3RoZXIgdGhyZWUgZm9vdCByYWlsIG1pZ2h0IGJvdGggYmUgcmVxdWlyZWQpLiBUaGVyZSBpcyBubyBuZWVkIHRvIG1hbnVmYWN0dXJlIG1vcmUgcmFpbHMgKG9yIG1vcmUgb2YgYW55IGtpbmQgb2YgcmFpbCkgdGhhbiBjYWxsZWQgZm9yIHRoZSBsaXN0IG9mIHJlcXVpcmVkIHJhaWxzLjxcL3A+XHJcblxyXG48cD5HaXZlbjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5OICgxICZsdDs9IE4gJmx0Oz0gNTApLCB0aGUgbnVtYmVyIG9mIGJvYXJkczxcL2xpPlxyXG5cdDxsaT5OIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciB0aGF0IHJlcHJlc2VudHMgdGhlIGxlbmd0aCBvZiBvbmUgc3VwcGxpZWQgYm9hcmQ8XC9saT5cclxuXHQ8bGk+UiAoMSAmbHQ7PSBSICZsdDs9IDEwMjMpLCB0aGUgbnVtYmVyIG9mIHJhaWxzPFwvbGk+XHJcblx0PGxpPlIgbGluZXMgZWFjaCBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgKDEgJmx0Oz0gcjxzdWI+aTxcL3N1Yj4gJmx0Oz0gMTI4KSB0aGF0IHJlcHJlc2VudHMgdGhlIGxlbmd0aCBvZiBhIHNpbmdsZSByZXF1aXJlZCBmZW5jZSByYWlsPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+dGhlbiBjYWxjdWxhdGUgYW5kIHByaW50IGFzIGEgc2luZ2xlIGludGVnZXIgb24gYSBsaW5lIHRoZSBtYXhpbXVtIHRvdGFsIG51bWJlciBvZiBmZW5jZSByYWlscyB0aGF0IGNhbiBiZSBjdXQgZnJvbSB0aGUgc3VwcGxpZWQgYm9hcmRzLiBPZiBjb3Vyc2UsIGl0IG1pZ2h0IG5vdCBiZSBwb3NzaWJsZSB0byBjdXQgYWxsIHRoZSBwb3NzaWJsZSByYWlscyBmcm9tIHRoZSBnaXZlbiBib2FyZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBOPFwvcD5cclxuXHJcbjxwPk4gc3Vic2VxdWVudCBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgc3VwcGxpZWQgbGVuZ3RoPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgUjxcL3A+XHJcblxyXG48cD5SIHN1YnNlcXVlbnQgbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHJlcXVpcmVkIGxlbmd0aDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGludGVnZXIgb24gYSBsaW5lLiBUaGUgaW50ZWdlciBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcmVxdWlyZWQgZmVuY2UgbGVuZ3RocyB0aGF0IGNhbiBiZSBjdXQgZnJvbSB0aGUgc3VwcGxpZWQgZmVuY2Ugc2VjdGlvbnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==