시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 630 239 203 40.845%

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만드려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작다. (1 ≤ N ≤ 10)

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

예제 입력 1

4
1 7
2 6
3 8
4 9

예제 출력 1

1

힌트

2, 3, 4번 재료를 사용한다면, 요리의 신맛은 2*3*4=24, 쓴맛은 6+8+9=23이 된다. 차이는 1이다.

W3sicHJvYmxlbV9pZCI6IjI5NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YjlkYlx1Yzc4OFx1YjI5NCBcdWM3NGNcdWMyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM5ZGNcdWQzMGNcdWFkNmNcdWI5YWMgXHVjNjk0XHViOWFjXHVjMGFjXHViODVjIFx1YmE4NVx1YzEzMVx1Yzc0NCBcdWIwYTBcdWI4MzhcdWM1YzhcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjNWM2XHVjNWM4XHViMzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2OTRcdWI5YWNcdWM1ZDAgXHViM2M0XHVjODA0XHVjNzQ0IFx1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YWUwOCBcdWIzYzRcdWM2MDFcdWM3NzRcdWM3NTggXHVjNTVlXHVjNWQwXHViMjk0IFx1YzdhY1x1YjhjY1x1YWMwMCBOXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMSBcdWM3YWNcdWI4Y2NcdWM3NTggXHVjMmUwXHViOWRiIFNcdWM2NDAgXHVjNGY0XHViOWRiIEJcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWVjXHViN2VjIFx1YzdhY1x1YjhjY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNjk0XHViOWFjXHVkNTYwIFx1YjU0YywgXHVhZGY4IFx1Yzc0Y1x1YzJkZFx1Yzc1OCBcdWMyZTBcdWI5ZGJcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWM3NTggXHVhY2YxXHVjNzc0XHVhY2UwLCBcdWM0ZjRcdWI5ZGJcdWM3NDAgXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWFjNzBcdWIwOTggXHVjNGY0IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjljZVx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YjNjNFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3YWNcdWI4Y2NcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YzExZVx1YzViNFx1YzExYyBcdWM2OTRcdWI5YWNcdWM3NTggXHVjMmUwXHViOWRiXHVhY2ZjIFx1YzRmNFx1YjlkYlx1Yzc1OCBcdWNjMjhcdWM3NzRcdWI5N2MgXHVjNzkxXHVhYzhjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViYjNjXHVjNzQ0IFx1YzY5NFx1YjlhY1x1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHVjMjE4XHViMjk0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzdhY1x1YjhjY1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJlMFx1YjlkYlx1YWNmYyBcdWM0ZjRcdWI5ZGJcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjNjk0XHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3YWNcdWI4Y2NcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjN2FjXHViOGNjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM2OTRcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzY5NFx1YjlhY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzQwIFx1YmFhOFx1YjQ1MCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC4mbmJzcDsoMSZuYnNwOyZsZTsgTiAmbGU7IDEwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmUwXHViOWRiXHVhY2ZjIFx1YzRmNFx1YjlkYlx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM2OTRcdWI5YWNcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+MiwgMywgNFx1YmM4OCBcdWM3YWNcdWI4Y2NcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0XHViYTc0LCBcdWM2OTRcdWI5YWNcdWM3NTggXHVjMmUwXHViOWRiXHVjNzQwIDIqMyo0PTI0LCBcdWM0ZjRcdWI5ZGJcdWM3NDAgNis4Kzk9MjNcdWM3NzQgXHViNDFjXHViMmU0LiBcdWNjMjhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQRVJLRVQiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1BlcmtldCZxdW90OyBpcyBhIHdpZGVseSBrbm93biBhbmQgZGVsaWNpb3VzIG1lYWwuIEZvciBwZXJrZXQgdG8gYmUgd2hhdCBpdCBpcywgY29va3MgbXVzdCBjYXJlZnVsbHkgY2hvb3NlIHRoZSBpbmdyZWRpZW50cyB0byBnZXQgdGhlIGZ1bGxlc3QgdGFzdGUgcG9zc2libGUgd2hpbGUga2VlcGluZyB0aGUgbWVhbCB0cmFkaXRpb25hbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgTiBpbmdyZWRpZW50cyBhdCB5b3VyIGRpc3Bvc2FsLiBGb3IgZWFjaCB3ZSBrbm93IGl0cyBzb3VybmVzcyBTIGFuZCBiaXR0ZXJuZXNzIEIuIFdoZW4gdXNpbmcgbXVsdGlwbGUgaW5ncmVkaWVudHMsIHRoZSB0b3RhbCBzb3VybmVzcyBpcyB0aGUgcHJvZHVjdCBvZiBzb3VybmVzcyBhbW91bnRzIG9mIGFsbCBpbmdyZWRpZW50cywgd2hpbGUgdGhlIHRvdGFsIGJpdHRlcm5lc3MgaXMgdGhlIHN1bSBvZiBiaXR0ZXJuZXNzIGFtb3VudHMgb2YgYWxsIGluZ3JlZGllbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBldmVyeW9uZSBrbm93cywgcGVya2V0IGlzIHN1cHBvc2VkIHRvIGJlIG5laXRoZXIgc291ciBub3IgYml0dGVyOyB3ZSB3YW50IHRvIGNob29zZSB0aGUgaW5ncmVkaWVudHMgc28gdGhhdCB0aGUgYWJzb2x1dGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHNvdXJuZXNzIGFuZCBiaXR0ZXJuZXNzIGlzIHRoZSBzbWFsbGVzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxzbywgaXQgaXMgbmVjZXNzYXJ5IHRvIHVzZSBhdCBsZWFzdCBvbmUgaW5ncmVkaWVudDsgeW91IGNhbiYjMzk7dCBzZXJ2ZSB3YXRlciBhcyB0aGUgbWFpbiBjb3Vyc2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwKSwgdGhlIG51bWJlciBvZiBpbmdyZWRpZW50cyBhdCBvdXIgZGlzcG9zYWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIHRoZSBzb3VybmVzcyBhbmQgYml0dGVybmVzcyBvZiBlYWNoIGluZ3JlZGllbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0LCBpZiB3ZSBtYWtlIGEgbWVhbCB3aXRoIGFsbCBpbmdyZWRpZW50cywgYm90aCB0aGUgc291cm5lc3MgYW5kIGJpdHRlcm5lc3Mgd2lsbCBiZSBsZXNzIHRoYW4gMTAwMDAwMDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIGRpZmZlcmVuY2UgYmV0d2VlbiBzb3VybmVzcyBhbmQgYml0dGVybmVzcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 3번