시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB69323421255248.069%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

1
3 10

예제 출력 1

7

예제 입력 2

2
3 8
5 8

예제 출력 2

1

예제 입력 3

4
1 7
2 6
3 8
4 9

예제 출력 3

1

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

W3sicHJvYmxlbV9pZCI6IjI5NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YjlkYlx1Yzc4OFx1YjI5NCBcdWM3NGNcdWMyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM5ZGNcdWQzMGNcdWFkNmNcdWI5YWMgXHVjNjk0XHViOWFjXHVjMGFjXHViODVjIFx1YmE4NVx1YzEzMVx1Yzc0NCBcdWIwYTBcdWI4MzhcdWM1YzhcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjNWM2XHVjNWM4XHViMzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2OTRcdWI5YWNcdWM1ZDAgXHViM2M0XHVjODA0XHVjNzQ0IFx1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YWUwOCBcdWIzYzRcdWM2MDFcdWM3NzRcdWM3NTggXHVjNTVlXHVjNWQwXHViMjk0IFx1YzdhY1x1YjhjY1x1YWMwMCBOXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHViM2M0XHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMSBcdWM3YWNcdWI4Y2NcdWM3NTggXHVjMmUwXHViOWRiIFNcdWM2NDAgXHVjNGY0XHViOWRiIEJcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWVjXHViN2VjIFx1YzdhY1x1YjhjY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNjk0XHViOWFjXHVkNTYwIFx1YjU0YywgXHVhZGY4IFx1Yzc0Y1x1YzJkZFx1Yzc1OCBcdWMyZTBcdWI5ZGJcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWM3NTggXHVhY2YxXHVjNzc0XHVhY2UwLCBcdWM0ZjRcdWI5ZGJcdWM3NDAgXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWFjNzBcdWIwOTggXHVjNGY0IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1YjljZVx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YjNjNFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3YWNcdWI4Y2NcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YzExZVx1YzViNFx1YzExYyBcdWM2OTRcdWI5YWNcdWM3NTggXHVjMmUwXHViOWRiXHVhY2ZjIFx1YzRmNFx1YjlkYlx1Yzc1OCBcdWNjMjhcdWM3NzRcdWI5N2MgXHVjNzkxXHVhYzhjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViYjNjXHVjNzQ0IFx1YzY5NFx1YjlhY1x1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHVjMjE4XHViMjk0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzdhY1x1YjhjY1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJlMFx1YjlkYlx1YWNmYyBcdWM0ZjRcdWI5ZGJcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjNjk0XHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3YWNcdWI4Y2NcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjN2FjXHViOGNjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM2OTRcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzY5NFx1YjlhY1x1Yzc1OCBcdWMyZTBcdWI5ZGJcdWFjZmMgXHVjNGY0XHViOWRiXHVjNzQwIFx1YmFhOFx1YjQ1MCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmUwXHViOWRiXHVhY2ZjIFx1YzRmNFx1YjlkYlx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM2OTRcdWI5YWNcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+MiwgMywgNFx1YmM4OCBcdWM3YWNcdWI4Y2NcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0XHViYTc0LCBcdWM2OTRcdWI5YWNcdWM3NTggXHVjMmUwXHViOWRiXHVjNzQwIDImdGltZXM7MyZ0aW1lczs0PTI0LCBcdWM0ZjRcdWI5ZGJcdWM3NDAgNis4Kzk9MjNcdWM3NzQgXHViNDFjXHViMmU0LiBcdWNjMjhcdWM3NzRcdWIyOTQgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyOTYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEVSS0VUIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtQZXJrZXQmcXVvdDsgaXMgYSB3aWRlbHkga25vd24gYW5kIGRlbGljaW91cyBtZWFsLiBGb3IgcGVya2V0IHRvIGJlIHdoYXQgaXQgaXMsIGNvb2tzIG11c3QgY2FyZWZ1bGx5IGNob29zZSB0aGUgaW5ncmVkaWVudHMgdG8gZ2V0IHRoZSBmdWxsZXN0IHRhc3RlIHBvc3NpYmxlIHdoaWxlIGtlZXBpbmcgdGhlIG1lYWwgdHJhZGl0aW9uYWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIE4gaW5ncmVkaWVudHMgYXQgeW91ciBkaXNwb3NhbC4gRm9yIGVhY2ggd2Uga25vdyBpdHMgc291cm5lc3MgUyBhbmQgYml0dGVybmVzcyBCLiBXaGVuIHVzaW5nIG11bHRpcGxlIGluZ3JlZGllbnRzLCB0aGUgdG90YWwgc291cm5lc3MgaXMgdGhlIHByb2R1Y3Qgb2Ygc291cm5lc3MgYW1vdW50cyBvZiBhbGwgaW5ncmVkaWVudHMsIHdoaWxlIHRoZSB0b3RhbCBiaXR0ZXJuZXNzIGlzIHRoZSBzdW0gb2YgYml0dGVybmVzcyBhbW91bnRzIG9mIGFsbCBpbmdyZWRpZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QXMgZXZlcnlvbmUga25vd3MsIHBlcmtldCBpcyBzdXBwb3NlZCB0byBiZSBuZWl0aGVyIHNvdXIgbm9yIGJpdHRlcjsgd2Ugd2FudCB0byBjaG9vc2UgdGhlIGluZ3JlZGllbnRzIHNvIHRoYXQgdGhlIGFic29sdXRlIGRpZmZlcmVuY2UgYmV0d2VlbiBzb3VybmVzcyBhbmQgYml0dGVybmVzcyBpcyB0aGUgc21hbGxlc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsc28sIGl0IGlzIG5lY2Vzc2FyeSB0byB1c2UgYXQgbGVhc3Qgb25lIGluZ3JlZGllbnQ7IHlvdSBjYW4mIzM5O3Qgc2VydmUgd2F0ZXIgYXMgdGhlIG1haW4gY291cnNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMCksIHRoZSBudW1iZXIgb2YgaW5ncmVkaWVudHMgYXQgb3VyIGRpc3Bvc2FsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNwYWNlLCB0aGUgc291cm5lc3MgYW5kIGJpdHRlcm5lc3Mgb2YgZWFjaCBpbmdyZWRpZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCwgaWYgd2UgbWFrZSBhIG1lYWwgd2l0aCBhbGwgaW5ncmVkaWVudHMsIGJvdGggdGhlIHNvdXJuZXNzIGFuZCBiaXR0ZXJuZXNzIHdpbGwgYmUgbGVzcyB0aGFuIDEwMDAwMDAwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBkaWZmZXJlbmNlIGJldHdlZW4gc291cm5lc3MgYW5kIGJpdHRlcm5lc3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgdGhpcmQgZXhhbXBsZSwgd2UgY2hvb3NlIHRoZSBsYXN0IHRocmVlIGluZ3JlZGllbnRzLiBUaGUgdG90YWwgc291cm5lc3MgaXMgdGhlbiAyJm1pZGRvdDszJm1pZGRvdDs0PTI0IGFuZCBiaXR0ZXJuZXNzIGlzIDYrOCs5PTIzLiBUaGUgZGlmZmVyZW5jZSBpcyAxLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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