시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 2 40.000%

문제

밑면이 반지름이 r인 원이고 윗면이 반지름이 R인 사발이 있다. (윗면을 뚫려있다) 그리고 옆면이 직선이다. N개의 사발이 주어져 있을 때, 이 사발을 적절한 순서로 쌓을 때 최소 높이를 구하는 프로그램을 작성하시오. (단 사발의 두께는 무시하는 걸로 하자)

사발의 쌓는 모양을 그림으로 표현하면 대략 다음과 같다.

입력

첫 번째 줄에는 사발의 개수 n(2<=n<=9)가 주어진다. 그리고 두 번째 줄부터 n+1번째 줄까지 각 사발의 정보가 주어지는데 각 줄에는 h,r,R 세 개의 정수가 빈칸을 사이에 두고 차례로 주어진다. h는 높이를 의미하고, r은 밑면의 반지름, R은 윗면의 반지름을 의미한다. (0 < h,r,R < 1000  , r<R)

출력

첫째 줄에 최소 높이를 출력한다. (단 결과를 버림하여 정수값으로 출력한다.)

예제 입력 1

3
50 30 80
35 25 70
40 10 90

예제 출력 1

55
W3sicHJvYmxlbV9pZCI6IjIwMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWJjMWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmMxMVx1YmE3NFx1Yzc3NCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgclx1Yzc3OCBcdWM2ZDBcdWM3NzRcdWFjZTAgXHVjNzE3XHViYTc0XHVjNzc0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCBSXHVjNzc4IFx1YzBhY1x1YmMxY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIChcdWM3MTdcdWJhNzRcdWM3NDQgXHViNmFiXHViODI0XHVjNzg4XHViMmU0KSBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNjA2XHViYTc0XHVjNzc0IFx1YzljMVx1YzEyMFx1Yzc3NFx1YjJlNC4gTlx1YWMxY1x1Yzc1OCBcdWMwYWNcdWJjMWNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMwYWNcdWJjMWNcdWM3NDQgXHVjODAxXHVjODA4XHVkNTVjIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHViNTRjIFx1Y2Q1Y1x1YzE4YyBcdWIxOTJcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWIyZTggXHVjMGFjXHViYzFjXHVjNzU4IFx1YjQ1MFx1YWVkOFx1YjI5NCBcdWJiMzRcdWMyZGNcdWQ1NThcdWIyOTQgXHVhYzc4XHViODVjIFx1ZDU1OFx1Yzc5MCk8XC9wPlxyXG48cD5cdWMwYWNcdWJjMWNcdWM3NTggXHVjMzEzXHViMjk0IFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViYTc0IFx1YjMwMFx1YjdiNSBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcbjxwPjxpbWcgd2lkdGg9XCI0MDZcIiBoZWlnaHQ9XCIxMTRcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvNGIucG5nXCIgXC8+PFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YmMxY1x1Yzc1OCBcdWFjMWNcdWMyMTggbigyJmx0Oz1uJmx0Oz05KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YWMwMSBcdWMwYWNcdWJjMWNcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IGgscixSIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YmU0OFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGhcdWIyOTQgXHViMTkyXHVjNzc0XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgclx1Yzc0MCBcdWJjMTFcdWJhNzRcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0LCBSXHVjNzQwIFx1YzcxN1x1YmE3NFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAoMCAmbHQ7IGgscixSICZsdDsgMTAwMCZuYnNwOyAsIHImbHQ7Uik8XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjMThjIFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWIyZTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1YmM4NFx1YjliY1x1ZDU1OFx1YzVlYyBcdWM4MTVcdWMyMThcdWFjMTJcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0Lik8XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwMDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCb3dsc3RhY2siLCJkZXNjcmlwdGlvbiI6IjxwPkJha2luZyBicmVhZCBpcyBteSBmYXZvdXJpdGUgc3BhcmUtdGltZSBwdXJzdWl0LiBJIGhhdmUgYSBudW1iZXIgb2Ygc3RhaW5sZXNzIHN0ZWVsIG1peGluZyBib3dscyB3aXRoIHN0cmFpZ2h0IHNpZGVzLCBhIGNpcmN1bGFyIGJvdHRvbSBhbmQgYSB3aWRlciBjaXJjdWxhciB0b3Agb3BlbmluZy4gR2VvbWV0cmljYWxseSwgbXkgYm93bHMgYXJlIHRydW5jYXRlZCBjaXJjdWxhciBjb25lcyBhbmQgZm9yIHRoaXMgcHJvYmxlbSwgdGhlIHRoaWNrbmVzcyBvZiB0aGUgbWV0YWwgbWF5IGJlIGRpc3JlZ2FyZGVkLjxcL3A+XHJcblxyXG48cD5JIHN0b3JlIHRoZXNlIGJvd2xzIHN0YWNrZWQgaW4gdGhlIG5hdHVyYWwgd2F5LCB0aGF0IGlzIHdpdGggYSBjb21tb24gdmVydGljYWwgYXhpcywgYW5kIEkgc3RhY2sgdGhlbSBpbiBhbiBvcmRlciB0aGF0IG1pbmltaXNlcyB0aGUgdG90YWwgaGVpZ2h0IG9mIHRoZSBzdGFjay4gRmluZGluZyB0aGlzIG1pbmltdW0gaXMgdGhlIHB1cnBvc2Ugb2YgeW91ciBwcm9ncmFtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGlzIGEgcG9zaXRpdmUgaW50ZWdlciwgdGVsbGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggb25lIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4sIHRoZSBudW1iZXIgb2YgYm93bHMgKDIgJmxlOyBuICZsZTsgOSkuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbiBsaW5lcyBlYWNoIGNvbnRhaW4gdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnMgaCxyLFIsIHNwZWNpZnlpbmcgdGhlIGhlaWdodCwgdGhlIGJvdHRvbSByYWRpdXMgYW5kIHRoZSB0b3AgcmFkaXVzIG9mIHRoZSBib3dsLCBhbmQgciAmbHQ7IFIgaG9sZHMgdHJ1ZS4gWW91IG1heSBhbHNvIGFzc3VtZSB0aGF0IGgscixSICZsdDsgMTAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBtaW5pbWFsIHN0YWNrIGhlaWdodCwgdHJ1bmNhdGVkIHRvIGFuIGludGVnZXIgKG5vdGU6IHRydW5jYXRlZCwgbm90IHJvdW5kZWQpLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA3XC80Yi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTRweDsgb3BhY2l0eTowLjk7IHdpZHRoOjQwNnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=