시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 363 73 36 13.139%

문제

N(1≤N≤50,000)개의 수조가 있다. 각각의 수조는 3차원 공간상에 존재한다. 수조에 대한 정보는 수조가 위치한 높이 b(0≤b≤1,000,000), 수조 자체의 높이 h(1≤h≤40,000), 수조의 가로길이 w(1≤w≤40,000), 수조의 세로길이 d(1≤d≤40,000)로 표현된다. 모든 수조의 아래에는 파이프가 달려 있고, 모든 파이프들은 하나로 연결되어 있다.

이러한 수조에 부피 V(1≤V≤2,000,000,000)만큼의 물을 넣으려고 한다. 수조들은 모두 파이프로 연결되어 있기 때문에, 전체 수조들의 제일 아래부터 차례로 물이 차게 된다. 문제의 편의를 위해서 파이프의 크기는 무시하기로 하자. 즉, 물은 파이프에는 들어가지 않고 수조에만 채워지는 것으로 간주한다. 이와 같이 물을 채웠을 때, 최종 수면의 높이를 구하려고 한다. 예를 들어 아래와 같은 경우에는 최종 수면의 높이 17이 된다.

수조들에 대한 정보와 물의 양이 주어졌을 때, 최종 수면의 높이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 수조의 b, h, w, d값이 주어진다. 제일 마지막 줄에는 물의 부피가 주어진다. 모든 입력은 정수이다.

출력

첫째 줄에 최종 수면의 높이를 소수점 아래 둘째 자리까지 출력한다. 셋째 자리에서 반올림한다. 만약 물의 양이 많을 경우에는 OVERFLOW를 출력한다.

예제 입력 1

4
11 7 5 1
15 6 4 1
5 8 5 1
19 4 8 1
78

예제 출력 1

17.00

힌트

W3sicHJvYmxlbV9pZCI6IjIxMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM4NzAiLCJkZXNjcmlwdGlvbiI6IjxwPk4oMSZsZTtOJmxlOzUwLDAwMClcdWFjMWNcdWM3NTggXHVjMjE4XHVjODcwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxOFx1Yzg3MFx1YjI5NCAzXHVjYzI4XHVjNmQwIFx1YWNmNVx1YWMwNFx1YzBjMVx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YzIxOFx1Yzg3MFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViMjk0IFx1YzIxOFx1Yzg3MFx1YWMwMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViMTkyXHVjNzc0IGIoMCZsZTtiJmxlOzEsMDAwLDAwMCksIFx1YzIxOFx1Yzg3MCBcdWM3OTBcdWNjYjRcdWM3NTggXHViMTkyXHVjNzc0IGgoMSZsZTtoJmxlOzQwLDAwMCksIFx1YzIxOFx1Yzg3MFx1Yzc1OCBcdWFjMDBcdWI4NWNcdWFlMzhcdWM3NzQgdygxJmxlO3cmbGU7NDAsMDAwKSwgXHVjMjE4XHVjODcwXHVjNzU4IFx1YzEzOFx1Yjg1Y1x1YWUzOFx1Yzc3NCBkKDEmbGU7ZCZsZTs0MCwwMDApXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIxOFx1Yzg3MFx1Yzc1OCBcdWM1NDRcdWI3OThcdWM1ZDBcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIFx1YjJlY1x1YjgyNCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI0ZTRcdWM3NDAgXHVkNTU4XHViMDk4XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMyMThcdWM4NzBcdWM1ZDAgXHViZDgwXHVkNTNjIFYoMSZsZTtWJmxlOzIsMDAwLDAwMCwwMDApXHViOWNjXHVkMDdjXHVjNzU4IFx1YmIzY1x1Yzc0NCBcdWIxMjNcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMyMThcdWM4NzBcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjODA0XHVjY2I0IFx1YzIxOFx1Yzg3MFx1YjRlNFx1Yzc1OCBcdWM4MWNcdWM3N2MgXHVjNTQ0XHViNzk4XHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWJiM2NcdWM3NzQgXHVjYzI4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViYjM4XHVjODFjXHVjNzU4IFx1ZDNiOFx1Yzc1OFx1Yjk3YyBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJiMzRcdWMyZGNcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNzkwLiBcdWM5ODksIFx1YmIzY1x1Yzc0MCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM1ZDBcdWIyOTQgXHViNGU0XHVjNWI0XHVhYzAwXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWMyMThcdWM4NzBcdWM1ZDBcdWI5Y2MgXHVjYzQ0XHVjNmNjXHVjOWMwXHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViYjNjXHVjNzQ0IFx1Y2M0NFx1YzZlMFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1Yzg4NSBcdWMyMThcdWJhNzRcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZDVjXHVjODg1IFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzQgMTdcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC93YXRlci5QTkdcIiBzdHlsZT1cImhlaWdodDozODRweDsgd2lkdGg6NDU1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjODcwXHViNGU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWM2NDAgXHViYjNjXHVjNzU4IFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWM4ODUgXHVjMjE4XHViYTc0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzIxOFx1Yzg3MFx1Yzc1OCBiLCBoLCB3LCBkXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODFjXHVjNzdjIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjNjXHVjNzU4IFx1YmQ4MFx1ZDUzY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjVcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjODg1IFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjMThjXHVjMjE4XHVjODEwIFx1YzU0NFx1Yjc5OCBcdWI0NThcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjMTRiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWJiM2NcdWM3NTggXHVjNTkxXHVjNzc0IFx1YjljZVx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgT1ZFUkZMT1dcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWxsIHRoZSBjaXN0ZXJucyEiLCJkZXNjcmlwdGlvbiI6IjxwPkR1cmluZyB0aGUgbmV4dCBjZW50dXJ5IGNlcnRhaW4gcmVnaW9ucyBvbiBlYXJ0aCB3aWxsIGV4cGVyaWVuY2Ugc2V2ZXJlIHdhdGVyIHNob3J0YWdlcy4gVGhlIG9sZCB0b3duIG9mIFVnYmFyIGhhcyBhbHJlYWR5IHN0YXJ0ZWQgdG8gcHJlcGFyZSBpdHNlbGYgZm9yIHRoZSB3b3JzdC4gUmVjZW50bHkgdGhleSBjcmVhdGVkIGEgbmV0d29yayBvZiBwaXBlcyBjb25uZWN0aW5nIHRoZSBjaXN0ZXJucyB0aGF0IGRpc3RyaWJ1dGUgd2F0ZXIgaW4gZWFjaCBuZWlnaGJvdXJob29kLCBtYWtpbmcgaXQgZWFzaWVyIHRvIGZpbGwgdGhlbSBhdCBvbmNlIGZyb20gYSBzaW5nbGUgc291cmNlIG9mIHdhdGVyLiBCdXQgaW4gY2FzZSBvZiB3YXRlciBzaG9ydGFnZSB0aGUgY2lzdGVybnMgYWJvdmUgYSBjZXJ0YWluIGxldmVsIHdpbGwgYmUgZW1wdHkgc2luY2UgdGhlIHdhdGVyIHdpbGwgZmxvdyB0byB0aGUgY2lzdGVybnMgYmVsb3cuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2lzdGVybnMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mzk0cHg7IHdpZHRoOjUwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIGJlZW4gYXNrZWQgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIGxldmVsIHRvIHdoaWNoIGNpc3Rlcm5zIHdpbGwgYmUgZmlsbGVkIHdpdGggYSBjZXJ0YWluIHZvbHVtZSBvZiB3YXRlciwgZ2l2ZW4gdGhlIGRpbWVuc2lvbnMgYW5kIHBvc2l0aW9uIG9mIGVhY2ggY2lzdGVybi4gVG8gc2ltcGxpZnkgd2Ugd2lsbCBuZWdsZWN0IHRoZSB2b2x1bWUgb2Ygd2F0ZXIgaW4gdGhlIHBpcGVzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggZm9yIGVhY2ggZGF0YSBzZXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIGNpc3Rlcm5zIGFuZCB0aGUgdm9sdW1lIG9mIHdhdGVyLDxcL2xpPlxyXG5cdDxsaT5jb21wdXRlcyB0aGUgbGV2ZWwgdG8gd2hpY2ggdGhlIGNpc3Rlcm5zIHdpbGwgYmUgZmlsbGVkIHdpdGggdGhlIGdpdmVuIGFtb3VudCBvZiB3YXRlciw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyBrLCAxICZsZTsgayAmbGU7IDMwLiBUaGUgZGF0YSBzZXQgZm9sbG93LjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBlYWNoIGRhdGEgc2V0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4sIHRoZSBudW1iZXIgb2YgY2lzdGVybnMsIDEgJmxlOyBuICZsZTsgNTAgMDAwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb25zaXN0cyBvZiA0IG5vbm5lZ2F0aXZlIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlczogYiwgaCwgdywgZCAtIHRoZSBiYXNlIGxldmVsIG9mIHRoZSBjaXN0ZXJuLCBpdHMgaGVpZ2h0LCB3aWR0aCBhbmQgZGVwdGggaW4gbWV0ZXJzLCByZXNwZWN0aXZlbHkuIFRoZSBpbnRlZ2VycyBzYXRpc2Z5IDAgJmxlOyBiICZsZTsgMTA8c3VwPjY8XC9zdXA+IGFuZCAxICZsZTsgaCZtaWRkb3Q7dyZtaWRkb3Q7ZCAmbGU7IDQwIDAwMC4gVGhlIGxhc3QgbGluZSBvZiB0aGUgZGF0YSBzZXQgY29udGFpbnMgYW4gaW50ZWdlciBWIC0gdGhlIHZvbHVtZSBvZiB3YXRlciBpbiBjdWJpYyBtZXRlcnMgdG8gYmUgaW5qZWN0ZWQgaW50byB0aGUgbmV0d29yay4gSW50ZWdlciBWIHNhdGlzZmllcyAxICZsZTsgdiAmbGU7IDImbWlkZG90OzEwPHN1cD45PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGV4YWN0bHkgZCBsaW5lcywgb25lIGxpbmUgZm9yIGVhY2ggZGF0YSBzZXQuPFwvcD5cclxuXHJcbjxwPkxpbmUgaSwgMSAmbGU7IGkgJmxlOyBkLCBzaG91bGQgY29udGFpbiB0aGUgbGV2ZWwgdGhhdCB0aGUgd2F0ZXIgd2lsbCByZWFjaCwgaW4gbWV0ZXJzLCByb3VuZGVkIHVwIHRvIHR3byBmcmFjdGlvbmFsIGRpZ2l0cywgb3IgdGhlIHdvcmQgJiMzOTtPVkVSRkxPVyYjMzk7LCBpZiB0aGUgdm9sdW1lIG9mIHdhdGVyIGV4Y2VlZHMgdGhlIHRvdGFsIGNhcGFjaXR5IG9mIHRoZSBjaXN0ZXJucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=