시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 7 7 58.333%

문제

상근이는 모니터를 여러개 붙여서 대형 모니터를 만드는 일을 하고 있다. 

고객은 대형 모니터의 가로, 세로 해상도(픽셀)과 가로 세로 크기(밀리미터)를 상근이에게 주문한다. 상근이는 고객의 주문 값보다 크거나 같은 해상도, 크거나 같은 크기의 대형 모니터를 만들어야 한다. 이때, 제조비가 최소가 되어야 한다.

대형 모니터는 항상 같은 종류의 모니터로 만들어야 한다. 대형 모니터의 해상도, 크기는 모니터를 붙인 형태로 각각을 더하면 되고, 가격은 사용한 모니터의 가격의 합이다.

상근이의 창고에는 모니터가 여러 종류가 있고, 각각의 해상도와 크기, 가격은 모두 알고 있다. 모니터를 회전 시켜서 대형 모니터를 만들 수 있다. 하지만, 대형 모니터에 포함된 모니터는 모두 같은 방향이어야 한다. 상근이는 모니터를 매우 많이 가지고 있어, 필요한 만큼 사용할 수 있다.

입력

첫재 줄에 대형 모니터의 가로 세로 해상도, 가로 세로 크기 rh, rv, sh, sv가 주어진다. 각 값은 100보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

다음 줄에는 상근이가 가지고 있는 모니터 종류의 개수 n이 주어진다. (1 ≤ n ≤ 100)

다음 n개 줄에는 각 모니터의 가로 세로 해상도, 가로 세로 크기, 가격 rh,i, rv,i, sh,i, sv,i, pi 가 주어진다. 이 값도 모두 100보다 크거나 같고, 10,000보다 작거나 같다.

출력

첫째 줄에 대형 모니터를 만드는 가격 중 가장 저렴한 가격을 출력한다.

예제 입력 1

1024 1024 300 300
3
1024 768 295 270 200
1280 1024 365 301 250
1280 800 350 270 210

예제 출력 1

250
W3sicHJvYmxlbV9pZCI6IjM1NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ2MTUgXHVjMmE0XHVkMDZjXHViOWIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YzVlY1x1YjdlY1x1YWMxYyBcdWJkOTlcdWM1ZWNcdWMxMWMgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YWMxZFx1Yzc0MCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHVjNzU4IFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1ZDU3NFx1YzBjMVx1YjNjNChcdWQ1M2RcdWMxNDApXHVhY2ZjIFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVkMDZjXHVhZTMwKFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMClcdWI5N2MgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzhmY1x1YmIzOFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YWMxZFx1Yzc1OCBcdWM4ZmNcdWJiMzggXHVhYzEyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVkNTc0XHVjMGMxXHViM2M0LCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjODFjXHVjODcwXHViZTQ0XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4XHVjNzU4IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHVjNzU4IFx1ZDU3NFx1YzBjMVx1YjNjNCwgXHVkMDZjXHVhZTMwXHViMjk0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWJkOTlcdWM3NzggXHVkNjE1XHVkMGRjXHViODVjIFx1YWMwMVx1YWMwMVx1Yzc0NCBcdWIzNTRcdWQ1NThcdWJhNzQgXHViNDE4XHVhY2UwLCBcdWFjMDBcdWFjYTlcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjYzNkXHVhY2UwXHVjNWQwXHViMjk0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVjODg1XHViOTU4XHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDU3NFx1YzBjMVx1YjNjNFx1YzY0MCBcdWQwNmNcdWFlMzAsIFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1ZDY4Y1x1YzgwNCBcdWMyZGNcdWNmMWNcdWMxMWMgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWJhYThcdWIyYzhcdWQxMzBcdWIyOTQgXHViYWE4XHViNDUwIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWQ1YTVcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YjllNFx1YzZiMCBcdWI5Y2VcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzViNCwgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjljY1x1ZDA3YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb25pdG9yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1MHB4OyB3aWR0aDoyODFweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjN2FjIFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHVjNzU4IFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVkNTc0XHVjMGMxXHViM2M0LCBcdWFjMDBcdWI4NWMgXHVjMTM4XHViODVjIFx1ZDA2Y1x1YWUzMCByPHN1Yj5oPFwvc3ViPiwgcjxzdWI+djxcL3N1Yj4sIHM8c3ViPmg8XC9zdWI+LCBzPHN1Yj52PFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWFjMTJcdWM3NDAgMTAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWIyYzhcdWQxMzAgXHVjODg1XHViOTU4XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yzc1OCBcdWFjMDBcdWI4NWMgXHVjMTM4XHViODVjIFx1ZDU3NFx1YzBjMVx1YjNjNCwgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzAsIFx1YWMwMFx1YWNhOSByPHN1Yj5oLGk8XC9zdWI+LCByPHN1Yj52LGk8XC9zdWI+LCBzPHN1Yj5oLGk8XC9zdWI+LCBzPHN1Yj52LGk8XC9zdWI+LCBwPHN1Yj5pPFwvc3ViPiBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHViM2M0IFx1YmFhOFx1YjQ1MCAxMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjMDBcdWFjYTkgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM4MDBcdWI4MzRcdWQ1NWMgXHVhYzAwXHVhY2E5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNTY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2lhbnQgU2NyZWVuIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHdvcmtpbmcgaW4gQWR2YW5jZWQgQ29tcHV0ZXIgTW9uaXRvcnMgKEFDTSksIEluYy4gVGhlIGNvbXBhbnkgaXMgYnVpbGRpbmcgYW5kIHNlbGxpbmcgZ2lhbnQgY29tcHV0ZXIgc2NyZWVucyB0aGF0IGFyZSBjb21wb3NlZCBmcm9tIG11bHRpcGxlIHNtYWxsZXIgc2NyZWVucy4gWW91ciBhcmUgcmVzcG9uc2libGUgZm9yIGRlc2lnbiBvZiB0aGUgc2NyZWVucyBmb3IgeW91ciBjdXN0b21lcnMuPFwvcD5cclxuXHJcbjxwPkN1c3RvbWVycyBvcmRlciBzY3JlZW5zIG9mIHRoZSBzcGVjaSBlZCBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCByZXNvbHV0aW9uIGluIHBpeGVscyBhbmQgYSBzcGVjaSBlZCBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBzaXplIGluIG1pbGxpbWV0ZXJzLiBZb3VyIHRhc2sgaXMgdG8gZGVzaWduIGEgc2NyZWVuIHRoYXQgaGFzIGEgcmVxdWlyZWQgcmVzb2x1dGlvbiBpbiBlYWNoIGRpbWVuc2lvbiBvciBtb3JlLCBhbmQgaGFzIHJlcXVpcmVkIHNpemUgaW4gZWFjaCBkaW1lbnNpb24gb3IgbW9yZSwgd2l0aCBhIG1pbmltYWwgcG9zc2libGUgcHJpY2UuIFRoZSBnaWFudCBzY3JlZW4gaXMgYWx3YXlzIGJ1aWx0IGFzIGEgZ3JpZCBvZiBtb25pdG9ycyBvZiB0aGUgc2FtZSB0eXBlLiBUaGUgdG90YWwgcmVzb2x1dGlvbiwgc2l6ZSwgYW5kIHByaWNlIG9mIHRoZSByZXN1bHRpbmcgc2NyZWVuIGlzIHNpbXBseSB0aGUgc3VtIG9mIHJlc29sdXRpb25zLCBzaXplcywgYW5kIHByaWNlcyBvZiB0aGUgc2NyZWVucyBpdCBpcyBidWlsdCBmcm9tLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBhIGNob2ljZSBvZiByZWd1bGFyIG1vbml0b3IgdHlwZXMgdGhhdCB5b3UgY2FuIG9yZGVyIGFuZCB5b3Uga25vdyB0aGVpciByZXNvbHV0aW9ucywgc2l6ZXMsIGFuZCBwcmljZXMuIFRoZSBzY3JlZW5zIG9mIGVhY2ggdHlwZSBjYW4gYmUgbW91bnRlZCBib3RoIHZlcnRpY2FsbHkgYW5kIGhvcml6b250YWxseSwgYnV0IHRoZSB3aG9sZSBnaWFudCBzY3JlZW4gbXVzdCBiZSBjb21wb3NlZCBvZiB0aGUgc2NyZWVucyBvZiB0aGUgc2FtZSB0eXBlIGluIHRoZSBzYW1lIG9yaWVudGF0aW9uLiBZb3UgY2FuIHVzZSBhcyBtYW55IHNjcmVlbnMgb2YgdGhlIGNob3NlbiB0eXBlIGFzIHlvdSBuZWVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21vbml0b3IucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTUwcHg7IHdpZHRoOjI4MXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgZm91ciBpbnRlZ2VyIG51bWJlcnMgcjxzdWI+aDxcL3N1Yj4sIHI8c3ViPnY8XC9zdWI+LCBzPHN1Yj5oPFwvc3ViPiwgYW5kIHM8c3ViPnY8XC9zdWI+IChhbGwgZnJvbSAxMDAgdG8gMTAgMDAwIGluY2x1c2l2ZSkgLSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCByZXNvbHV0aW9uIGFuZCBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBzaXplIG9mIHRoZSBzY3JlZW4geW91IGhhdmUgdG8gYnVpbGQsIHJlc3BlY3RpdmVseS4gVGhlIG5leHQgbGluZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciBuICgxICZsZTsgbiAmbGU7IDEwMCkgLSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzY3JlZW4gdHlwZXMgYXZhaWxhYmxlIHRvIHlvdS4gVGhlIG5leHQgbiBsaW5lcyBjb250YWluIGRlc2NyaXB0aW9ucyBvZiB0aGUgYXZhaWxhYmxlIHNjcmVlbiB0eXBlcy4gRWFjaCBkZXNjcmlwdGlvbiBvY2N1cGllcyBvbmUgbGluZSBhbmQgY29uc2lzdHMgb2YgZml2ZSBpbnRlZ2VyIG51bWJlcnMgLSByPHN1Yj5oLGk8XC9zdWI+LCByPHN1Yj52LGk8XC9zdWI+LCBzPHN1Yj5oLGk8XC9zdWI+LCBzPHN1Yj52LGk8XC9zdWI+LCBwPHN1Yj5pPFwvc3ViPiAoYWxsIGZyb20gMTAwIHRvIDEwIDAwMCBpbmNsdXNpdmUpLCB3aGVyZSBmaXJzdCBmb3VyIG51bWJlcnMgYXJlIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIHJlc29sdXRpb24gYW5kIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIHNpemUgb2YgaS10aCBzY3JlZW4gdHlwZSwgYW5kIHA8c3ViPmk8XC9zdWI+IGlzIHRoZSBwcmljZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0byB0aGUgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIgLSB0aGUgbWluaW1hbCBwcmljZSBvZiB0aGUgc3BlY2lmaWVkIGdpYW50IHNjcmVlbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=