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

문제

유명 편의점 체인점 세븐25는 삼각 김밥을 전국에서 가장 싸게 판매하고 있다. 

이 회사의 직원들은 삼각 김밥의 가격을 전국 최저가를 유지하기 위해 매일 근처의 편의점을 방문한다. 그리고 나서 세븐25의 삼각 김밥보다 싼 가격을 발견하면, 삼각 김밥의 가격을 그 가격으로 바꿔 최저가를 유지한다.

매일 아침, 점심, 저녁으로 삼각 김밥을 먹는 상근이와 정인이는 정말 세븐25가 제일 싼지 궁금해졌다. 

이들은 학교 근처에 있는 세븐 25와 세븐 25를 제외한 서로 다른 N개의 편의점 체인을 방문 할 것이다. 이 편의점을 방문하면서 세븐25보다 싼 삼각김밥을 찾을 것이다. 또, 전체 편의점에서 가장 싼 삼각 김밥은 어디인지 찾을 것이다.

어느 편의점의 삼각 김밥이 제일 싼지 고객들이 쉽게 알지 못하기 하기 위해서, 모든 편의점은 삼각 김밥의 가격을 다음과 같이 표시한다. "삼각 김밥 Y그램 당 X원"

상근이와 정인이는 삼각 김밥을 1,000그램 살 것이다.

세븐 25의 삼각 김밥 가격과, 다른 N개 편의점의 삼각 김밥 가격이 주어졌을 때, 1,000그램의 삼각 김밥을 가장 싸게 사려면 얼마면 되는지 구하는 프로그램을 작성하시오.

삼각 김밥은 여러 군데에서 돌아가면서 사도 되고, 세븐 25와 N개 편의점 이외의 다른 곳에서는 살 수 없다.

입력

첫째 줄에 세븐25의 삼각 김밥 가격 정보 X와 Y가 주어진다. (Y그램 당 X원) (1 ≤ X ≤ 100, 1 ≤ Y ≤ 1,000)

둘째 줄에는 세븐25를 제외한 편의점의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 i번째 편의점의 삼각 김밥 가격 정보 Xi와 Yi가 주어진다. (Yi그램 당 Xi원) (1 ≤ Xi ≤ 100, 1 ≤ Yi ≤ 1,000)

출력

첫째 줄에 삼각 김밥 1,000그램 가격의 최저가를 출력한다. 정답과의 오차는 0.01까지 허용한다.

예제 입력 1

5 100
3
4 100
3 100
7 100

예제 출력 1

30.00

예제 입력 2

13 6
5
56 679
35 120
99 999
56 73
37 532

예제 출력 2

69.55

예제 입력 3

100 5
3
99 8
65 14
78 10

예제 출력 3

4642.86
W3sicHJvYmxlbV9pZCI6IjI3ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWJhODUgXHVkM2I4XHVjNzU4XHVjODEwIFx1Y2NiNFx1Yzc3OFx1YzgxMCBcdWMxMzhcdWJlMTAyNVx1YjI5NCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1XHVjNzQ0IFx1YzgwNFx1YWQ2ZFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjMmY4XHVhYzhjIFx1ZDMxMFx1YjllNFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQ2OGNcdWMwYWNcdWM3NTggXHVjOWMxXHVjNmQwXHViNGU0XHVjNzQwIFx1YzBiY1x1YWMwMSBcdWFlNDBcdWJjMjVcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzQ0IFx1YzgwNFx1YWQ2ZCBcdWNkNWNcdWM4MDBcdWFjMDBcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWI5ZTRcdWM3N2MgXHVhZGZjXHVjYzk4XHVjNzU4IFx1ZDNiOFx1Yzc1OFx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwOThcdWMxMWMgXHVjMTM4XHViZTEwMjVcdWM3NTggXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNVx1YmNmNFx1YjJlNCBcdWMyZmMgXHVhYzAwXHVhY2E5XHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU1OFx1YmE3NCwgXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNVx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVhZGY4IFx1YWMwMFx1YWNhOVx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmZDQgXHVjZDVjXHVjODAwXHVhYzAwXHViOTdjIFx1YzcyMFx1YzljMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OCwgXHVjODEwXHVjMmVjLCBcdWM4MDBcdWIxNDFcdWM3M2NcdWI4NWMgXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNVx1Yzc0NCBcdWJhMzlcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM4MTVcdWI5ZDAgXHVjMTM4XHViZTEwMjVcdWFjMDAgXHVjODFjXHVjNzdjIFx1YzJmY1x1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWQ1NTlcdWFkNTAgXHVhZGZjXHVjYzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMxMzhcdWJlMTAgMjVcdWM2NDAgXHVjMTM4XHViZTEwIDI1XHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IE5cdWFjMWNcdWM3NTggXHVkM2I4XHVjNzU4XHVjODEwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWJjMjlcdWJiMzggXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1ZDNiOFx1Yzc1OFx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWJhNzRcdWMxMWMgXHVjMTM4XHViZTEwMjVcdWJjZjRcdWIyZTQgXHVjMmZjIFx1YzBiY1x1YWMwMVx1YWU0MFx1YmMyNVx1Yzc0NCBcdWNjM2VcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YzgwNFx1Y2NiNCBcdWQzYjhcdWM3NThcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzJmYyBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1XHVjNzQwIFx1YzViNFx1YjUxNFx1Yzc3OFx1YzljMCBcdWNjM2VcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHVkM2I4XHVjNzU4XHVjODEwXHVjNzU4IFx1YzBiY1x1YWMwMSBcdWFlNDBcdWJjMjVcdWM3NzQgXHVjODFjXHVjNzdjIFx1YzJmY1x1YzljMCBcdWFjZTBcdWFjMWRcdWI0ZTRcdWM3NzQgXHVjMjdkXHVhYzhjIFx1YzU0Y1x1YzljMCBcdWJhYmJcdWQ1NThcdWFlMzAgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViYWE4XHViNGUwIFx1ZDNiOFx1Yzc1OFx1YzgxMFx1Yzc0MCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC4gJnF1b3Q7XHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNSBZXHVhZGY4XHViN2E4IFx1YjJmOSBYXHVjNmQwJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNVx1Yzc0NCAxLDAwMFx1YWRmOFx1YjdhOCBcdWMwYjQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWJlMTAgMjVcdWM3NTggXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNSBcdWFjMDBcdWFjYTlcdWFjZmMsIFx1YjJlNFx1Yjk3OCBOXHVhYzFjIFx1ZDNiOFx1Yzc1OFx1YzgxMFx1Yzc1OCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1IFx1YWMwMFx1YWNhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCAxLDAwMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWMyZjhcdWFjOGMgXHVjMGFjXHViODI0XHViYTc0IFx1YzViY1x1YjljOFx1YmE3NCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzBiY1x1YWMwMSBcdWFlNDBcdWJjMjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWQ3MFx1YjM3MFx1YzVkMFx1YzExYyBcdWIzY2NcdWM1NDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVjMGFjXHViM2M0IFx1YjQxOFx1YWNlMCwgXHVjMTM4XHViZTEwIDI1XHVjNjQwIE5cdWFjMWMgXHVkM2I4XHVjNzU4XHVjODEwIFx1Yzc3NFx1YzY3OFx1Yzc1OCBcdWIyZTRcdWI5NzggXHVhY2YzXHVjNWQwXHVjMTFjXHViMjk0IFx1YzBiNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzhcdWJlMTAyNVx1Yzc1OCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1IFx1YWMwMFx1YWNhOSBcdWM4MTVcdWJjZjQgWFx1YzY0MCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFlcdWFkZjhcdWI3YTggXHViMmY5IFhcdWM2ZDApICgxICZsZTsgWCAmbGU7IDEwMCwgMSAmbGU7IFkgJmxlOyAxLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzhcdWJlMTAyNVx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVkM2I4XHVjNzU4XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWQzYjhcdWM3NThcdWM4MTBcdWM3NTggXHVjMGJjXHVhYzAxIFx1YWU0MFx1YmMyNSBcdWFjMDBcdWFjYTkgXHVjODE1XHViY2Y0IFg8c3ViPmk8XC9zdWI+XHVjNjQwIFk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFk8c3ViPmk8XC9zdWI+XHVhZGY4XHViN2E4IFx1YjJmOSBYPHN1Yj5pPFwvc3ViPlx1YzZkMCkgKDEgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwgMSAmbGU7IFk8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYmNcdWFjMDEgXHVhZTQwXHViYzI1IDEsMDAwXHVhZGY4XHViN2E4IFx1YWMwMFx1YWNhOVx1Yzc1OCBcdWNkNWNcdWM4MDBcdWFjMDBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjNjI0XHVjYzI4XHViMjk0Jm5ic3A7MC4wMVx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc4MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1PUlRBREVMQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIE5hdGlvbmFsIFN1cGVybWFya2V0IENoYWluIChOU0MpIGxpa2VzIHRvIGJvYXN0IHRoYXQgaXQgaGFzIHRoZSBsb3dlc3QgcHJpY2UgZm9yIG1vcnRhZGVsbGEgaW4gdGhlIGNvdW50cnkuIEluIGZhY3QsIGlmIGEgY3VzdG9tZXIgbWFuYWdlcyB0byBmaW5kIGNoZWFwZXIgbW9ydGFkZWxsYSBpbiBhbnkgb3RoZXIgY2hhaW4sIHRoZSBOU0Mgd2lsbCBtYXRjaCB0aGUgcHJpY2UgZm9yIHRoYXQgY3VzdG9tZXIuPFwvcD5cclxuXHJcbjxwPk1hdGVqIGFuZCBGaWxpcCBkZWNpZGVkIHRvIGFjY2VwdCB0aGF0IGNoYWxsZW5nZS4gVGhleSB3aWxsIHZpc2l0IE4gZGlmZmVyZW50IHN1cGVybWFya2V0IGNoYWlucyBpbiBvcmRlciB0byBmaW5kIG1vcnRhZGVsbGEgbm90IG9ubHkgY2hlYXBlciB0aGFuIHRoZSBvbmUgaW4gTlNDLCBidXQgdGhlIGNoZWFwZXN0IG9uIHRoZSBtYXJrZXQuIElmIHRoZXkgYXJlIHN1Y2Nlc3NmdWwsIHRoZXkgd2lsbCBiZSBhYmxlIHRvIGJ1eSB0aGUgY2hlYXBlc3QgbW9ydGFkZWxsYSBpbiBhbiBOU0MgYnJhbmNoIGNsb3NlIHRvIHRoZWlyIHNjaG9vbC48XC9wPlxyXG5cclxuPHA+TlNDIHdhcyBob3BpbmcgdGhhdCBubyBvbmUgd291bGQgYmUgYWJsZSB0byBmaW5kIGNoZWFwZXIgbW9ydGFkZWxsYSBzaW5jZSBhbGwgc3VwZXJtYXJrZXQgY2hhaW5zIChpbmNsdWRpbmcgTlNDKSBleHByZXNzIG1vcnRhZGVsbGEgcHJpY2VzIGluIGEgY29udm9sdXRlZCB3YXk6IFggZG9sbGFycyBmb3IgWSBncmFtcyBvZiBtb3J0YWRlbGxhLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8sIGdpdmVuIG1vcnRhZGVsbGEgcHJpY2VzIGluIE5TQyBhcyB3ZWxsIGFzIHRoZSByZW1haW5pbmcgTiBjaGFpbnMsIGRldGVybWluZSB0aGUgcHJpY2UgdGhhdCBNYXRlaiBhbmQgRmlsaXAgd2lsbCBoYXZlIHRvIHBheSBmb3IgMTAwMCBncmFtcyBvZiBtb3J0YWRlbGxhIGluIHRoZSBOU0MgY2xvc2UgdG8gdGhlaXIgc2Nob29sLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIFg8c3ViPk5TQzxcL3N1Yj4gKDEgJmxlOyBYPHN1Yj5OU0M8XC9zdWI+ICZsZTsgMTAwKSBhbmQgWTxzdWI+TlNDPFwvc3ViPiAoMSAmbGU7IFk8c3ViPk5TQzxcL3N1Yj4gJmxlOyAxMDAwKSwgd2hlcmUgWDxzdWI+TlNDPFwvc3ViPiBpcyB0aGUgcHJpY2Ugb2YgWTxzdWI+TlNDPFwvc3ViPiBncmFtcyBvZiBtb3J0YWRlbGxhIGluIHRoZSBOU0MgY2hhaW4uPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2Ygc3VwZXJtYXJrZXQgY2hhaW5zIChleGNsdWRpbmcgTlNDKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIFg8c3ViPmk8XC9zdWI+ICgxICZsZTsgWDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApIGFuZCBZPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IFk8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMCksIGk9MS4uTiwgd2hlcmUgWDxzdWI+aTxcL3N1Yj4gaXMgdGhlIHByaWNlIG9mIFk8c3ViPmk8XC9zdWI+IGdyYW1zIG9mIG1vcnRhZGVsbGEgaW4gdGhlIGk8c3VwPnRoPFwvc3VwPiBzdXBlcm1hcmtldCBjaGFpbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1ZXN0ZWQgcmVhbCBudW1iZXIgKHByaWNlKS4gSXQgaXMgYWxsb3dlZCB0byBkaWZmZXIgYXQgbW9zdCAwLjAxIGZyb20gdGhlIGV4YWN0IHNvbHV0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 1번