시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjM1NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ2MTUgXHVjMmE0XHVkMDZjXHViOWIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YzVlY1x1YjdlY1x1YWMxYyBcdWJkOTlcdWM1ZWNcdWMxMWMgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YWMxZFx1Yzc0MCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHVjNzU4IFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1ZDU3NFx1YzBjMVx1YjNjNChcdWQ1M2RcdWMxNDApXHVhY2ZjIFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVkMDZjXHVhZTMwKFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMClcdWI5N2MgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzhmY1x1YmIzOFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YWMxZFx1Yzc1OCBcdWM4ZmNcdWJiMzggXHVhYzEyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVkNTc0XHVjMGMxXHViM2M0LCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWIzMDBcdWQ2MTUgXHViYWE4XHViMmM4XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzgxY1x1Yzg3MFx1YmU0NFx1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWJhYThcdWIyYzhcdWQxMzBcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yzc1OCBcdWQ1NzRcdWMwYzFcdWIzYzQsIFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJhYThcdWIyYzhcdWQxMzBcdWI5N2MgXHViZDk5XHVjNzc4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWFjMDFcdWFjMDFcdWM3NDQgXHViMzU0XHVkNTU4XHViYTc0IFx1YjQxOFx1YWNlMCwgXHVhYzAwXHVhY2E5XHVjNzQwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWJhYThcdWIyYzhcdWQxMzBcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1Y2MzZFx1YWNlMFx1YzVkMFx1YjI5NCBcdWJhYThcdWIyYzhcdWQxMzBcdWFjMDAgXHVjNWVjXHViN2VjIFx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQ1NzRcdWMwYzFcdWIzYzRcdWM2NDAgXHVkMDZjXHVhZTMwLCBcdWFjMDBcdWFjYTlcdWM3NDAgXHViYWE4XHViNDUwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWQ2OGNcdWM4MDQgXHVjMmRjXHVjZjFjXHVjMTFjIFx1YjMwMFx1ZDYxNSBcdWJhYThcdWIyYzhcdWQxMzBcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViYWE4XHViMmM4XHVkMTMwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHViYzI5XHVkNWE1XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWI5ZTRcdWM2YjAgXHViOWNlXHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YjQsIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWI5Y2NcdWQwN2MgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9uaXRvci5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTBweDsgd2lkdGg6MjgxcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yzc1OCBcdWFjMDBcdWI4NWMgXHVjMTM4XHViODVjIFx1ZDU3NFx1YzBjMVx1YjNjNCwgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzAgcjxzdWI+aDxcL3N1Yj4sIHI8c3ViPnY8XC9zdWI+LCBzPHN1Yj5oPFwvc3ViPiwgczxzdWI+djxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVhYzEyXHVjNzQwIDEwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViMmM4XHVkMTMwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJhYThcdWIyYzhcdWQxMzBcdWM3NTggXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWQ1NzRcdWMwYzFcdWIzYzQsIFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWMgXHVkMDZjXHVhZTMwLCBcdWFjMDBcdWFjYTkgcjxzdWI+aCxpPFwvc3ViPiwgcjxzdWI+dixpPFwvc3ViPiwgczxzdWI+aCxpPFwvc3ViPiwgczxzdWI+dixpPFwvc3ViPiwgcDxzdWI+aTxcL3N1Yj4gXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1YjNjNCBcdWJhYThcdWI0NTAgMTAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNjE1IFx1YmFhOFx1YjJjOFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzAwXHVhY2E5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjODAwXHViODM0XHVkNTVjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzU2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdpYW50IFNjcmVlbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB3b3JraW5nIGluIEFkdmFuY2VkIENvbXB1dGVyIE1vbml0b3JzIChBQ00pLCBJbmMuIFRoZSBjb21wYW55IGlzIGJ1aWxkaW5nIGFuZCBzZWxsaW5nIGdpYW50IGNvbXB1dGVyIHNjcmVlbnMgdGhhdCBhcmUgY29tcG9zZWQgZnJvbSBtdWx0aXBsZSBzbWFsbGVyIHNjcmVlbnMuIFlvdXIgYXJlIHJlc3BvbnNpYmxlIGZvciBkZXNpZ24gb2YgdGhlIHNjcmVlbnMgZm9yIHlvdXIgY3VzdG9tZXJzLjxcL3A+XHJcblxyXG48cD5DdXN0b21lcnMgb3JkZXIgc2NyZWVucyBvZiB0aGUgc3BlY2kgZWQgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgcmVzb2x1dGlvbiBpbiBwaXhlbHMgYW5kIGEgc3BlY2kgZWQgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgc2l6ZSBpbiBtaWxsaW1ldGVycy4gWW91ciB0YXNrIGlzIHRvIGRlc2lnbiBhIHNjcmVlbiB0aGF0IGhhcyBhIHJlcXVpcmVkIHJlc29sdXRpb24gaW4gZWFjaCBkaW1lbnNpb24gb3IgbW9yZSwgYW5kIGhhcyByZXF1aXJlZCBzaXplIGluIGVhY2ggZGltZW5zaW9uIG9yIG1vcmUsIHdpdGggYSBtaW5pbWFsIHBvc3NpYmxlIHByaWNlLiBUaGUgZ2lhbnQgc2NyZWVuIGlzIGFsd2F5cyBidWlsdCBhcyBhIGdyaWQgb2YgbW9uaXRvcnMgb2YgdGhlIHNhbWUgdHlwZS4gVGhlIHRvdGFsIHJlc29sdXRpb24sIHNpemUsIGFuZCBwcmljZSBvZiB0aGUgcmVzdWx0aW5nIHNjcmVlbiBpcyBzaW1wbHkgdGhlIHN1bSBvZiByZXNvbHV0aW9ucywgc2l6ZXMsIGFuZCBwcmljZXMgb2YgdGhlIHNjcmVlbnMgaXQgaXMgYnVpbHQgZnJvbS48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgYSBjaG9pY2Ugb2YgcmVndWxhciBtb25pdG9yIHR5cGVzIHRoYXQgeW91IGNhbiBvcmRlciBhbmQgeW91IGtub3cgdGhlaXIgcmVzb2x1dGlvbnMsIHNpemVzLCBhbmQgcHJpY2VzLiBUaGUgc2NyZWVucyBvZiBlYWNoIHR5cGUgY2FuIGJlIG1vdW50ZWQgYm90aCB2ZXJ0aWNhbGx5IGFuZCBob3Jpem9udGFsbHksIGJ1dCB0aGUgd2hvbGUgZ2lhbnQgc2NyZWVuIG11c3QgYmUgY29tcG9zZWQgb2YgdGhlIHNjcmVlbnMgb2YgdGhlIHNhbWUgdHlwZSBpbiB0aGUgc2FtZSBvcmllbnRhdGlvbi4gWW91IGNhbiB1c2UgYXMgbWFueSBzY3JlZW5zIG9mIHRoZSBjaG9zZW4gdHlwZSBhcyB5b3UgbmVlZC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb25pdG9yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1MHB4OyB3aWR0aDoyODFweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGZvdXIgaW50ZWdlciBudW1iZXJzIHI8c3ViPmg8XC9zdWI+LCByPHN1Yj52PFwvc3ViPiwgczxzdWI+aDxcL3N1Yj4sIGFuZCBzPHN1Yj52PFwvc3ViPiAoYWxsIGZyb20gMTAwIHRvIDEwIDAwMCBpbmNsdXNpdmUpIC0gaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgcmVzb2x1dGlvbiBhbmQgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgc2l6ZSBvZiB0aGUgc2NyZWVuIHlvdSBoYXZlIHRvIGJ1aWxkLCByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBudW1iZXIgbiAoMSAmbGU7IG4gJmxlOyAxMDApIC0gdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc2NyZWVuIHR5cGVzIGF2YWlsYWJsZSB0byB5b3UuIFRoZSBuZXh0IG4gbGluZXMgY29udGFpbiBkZXNjcmlwdGlvbnMgb2YgdGhlIGF2YWlsYWJsZSBzY3JlZW4gdHlwZXMuIEVhY2ggZGVzY3JpcHRpb24gb2NjdXBpZXMgb25lIGxpbmUgYW5kIGNvbnNpc3RzIG9mIGZpdmUgaW50ZWdlciBudW1iZXJzIC0gcjxzdWI+aCxpPFwvc3ViPiwgcjxzdWI+dixpPFwvc3ViPiwgczxzdWI+aCxpPFwvc3ViPiwgczxzdWI+dixpPFwvc3ViPiwgcDxzdWI+aTxcL3N1Yj4gKGFsbCBmcm9tIDEwMCB0byAxMCAwMDAgaW5jbHVzaXZlKSwgd2hlcmUgZmlyc3QgZm91ciBudW1iZXJzIGFyZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCByZXNvbHV0aW9uIGFuZCBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBzaXplIG9mIGktdGggc2NyZWVuIHR5cGUsIGFuZCBwPHN1Yj5pPFwvc3ViPiBpcyB0aGUgcHJpY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdG8gdGhlIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIC0gdGhlIG1pbmltYWwgcHJpY2Ugb2YgdGhlIHNwZWNpZmllZCBnaWFudCBzY3JlZW4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d