시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1484 311 233 23.971%

문제

전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.

풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이 때, 모든 풍선을 달아주는데 필요한 이동 거리의 최소값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 

다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 DA, B로부터 떨어진 거리 DB (0 ≤ DA, DB ≤ 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σi Ki ≤ A+B.

입력의 마지막 줄에는 0이 세 개 주어진다.

출력

각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최소값을 출력한다. 이 때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.

예제 입력 1

3 15 35
10 20 10
10 10 30
10 40 10
0 0 0

예제 출력 1

300
W3sicHJvYmxlbV9pZCI6IjQ3MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0OGRcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMCBcdWIzMDBcdWQ2OGNcdWM1ZDBcdWMxMWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3YyBcdWQzMDBcdWM3NDAgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjOWMxXHVjODExIFx1YjJlY1x1YzU0NFx1YzhmY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzkwXHVjNmQwIFx1YmQwOVx1YzBhY1x1Yzc5MFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWJjMjkgQVx1YzY0MCBcdWJjMjkgQlx1YzVkMCBcdWJjZjRcdWFkMDBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTVjIFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NzRcdWFjZTAsIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1ZDMwMFx1Yzc0MCBcdWJjMjkgQVx1YzVkMCBcdWFjMDBcdWFlNWRcdWFjZTAsIFx1YzViNFx1YjVhNCBcdWQzMDBcdWM3NDAgQlx1YzVkMCBcdWIzNTQgXHVhYzAwXHVhZTVkXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YjJlY1x1YzU0NFx1YzkxOFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWJjMjkgQVx1YzY0MCBCXHViODVjXHViZDgwXHVkMTMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViMmVjXHVjNTQ0XHVjOGZjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3NzRcdWIzZDkgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViMmVjXHVjNTQ0XHVjOGZjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHViOWNlXHVhY2UwLCBcdWQ0OGRcdWMxMjBcdWM3NDAgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWIyZWNcdWM1NDRcdWM5MDBcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViMmVjXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhYzcwXHViOWFjXHViMjk0IFx1ZDMwMFx1Yzc3NCBBXHVjNjQwIEJcdWI4NWNcdWJkODBcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhY1x1YzY0MCBcdWFjMTlcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWM1NDRcdWM4ZmNcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQwIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVkNDhkXHVjMTIwIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWI0ZTRcdWFjZTAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzAwXHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMSwwMDApXHVhY2ZjIFx1YmMyOSBBXHVjNjQwIEJcdWM1ZDAgXHViY2Y0XHVhZDAwXHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWMyMTggQSwgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgQSwgQiAmbGU7IDEwLDAwMCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDMwMFx1YzVkMFx1YWM4YyBcdWIyZWNcdWM1NDRcdWM5MThcdWM1N2NcdWQ1NThcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YzIxOCBLXHVjNjQwIFx1YmMyOSBBXHViODVjXHViZDgwXHVkMTMwIFx1YjVhOFx1YzViNFx1YzljNCBcdWFjNzBcdWI5YWMgRDxzdWI+QTxcL3N1Yj4sIEJcdWI4NWNcdWJkODBcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBEPHN1Yj5CPFwvc3ViPiAoMCAmbGU7IEQ8c3ViPkE8XC9zdWI+LCBEPHN1Yj5CPFwvc3ViPiAmbGU7IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWJkODBcdWM4NzFcdWQ1NWMgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjOTg5LCAmU2lnbWE7PHN1Yj5pPFwvc3ViPiBLPHN1Yj5pPFwvc3ViPiAmbGU7IEErQi48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWMxMzggXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YmFhOFx1YjRlMCBcdWQzMDBcdWM1ZDBcdWFjOGMgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjJlY1x1YzU0NFx1YzhmY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjJlY1x1YzU0NFx1YzhmY1x1YWNlMCBcdWJjMjkgQVx1YjA5OCBCXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjOTg5LCBcdWJjMjkgQVx1YzY0MCBCXHVjNWQwXHVjMTFjIFx1ZDMwMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhYzcwXHViOWFjXHViOWNjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NzE2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsbG9vbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHlvdSBrbm93LCBiYWxsb29ucyBhcmUgaGFuZGVkIG91dCBkdXJpbmcgdGhpcyBjb250ZXN0IHRvIHRlYW1zIGFzIHRoZXkgc29sdmUgcHJvYmxlbXMuIEhvd2V2ZXIsIGluIHRoZSBwYXN0IHRoaXMgaGFzIHNvbWV0aW1lcyBwcmVzZW50ZWQgY2hhbGxlbmdpbmcgbG9naXN0aWNhbCBwcm9ibGVtcy48XC9wPlxyXG5cclxuPHA+T25lIGNvbnRlc3QgaG9zdGluZyBzaXRlIG1haW50YWluZWQgdHdvIHJvb21zLCBBIGFuZCBCLCBlYWNoIGNvbnRhaW5pbmcgYSBzdXBwbHkgb2YgYmFsbG9vbnMuIFRoZXJlIHdlcmUgTiB0ZWFtcyBhdHRlbmRpbmcgdGhlIGNvbnRlc3QsIGVhY2ggc2l0dGluZyBpbiBkaWZmZXJlbnQgbG9jYXRpb25zLCBzb21lIGJlaW5nIGNsb3NlciB0byByb29tIEEsIGFuZCBvdGhlcnMgdG8gcm9vbSBCLiBHaXZlbiB0aGUgbnVtYmVyIG9mIGJhbGxvb25zIG5lZWRlZCBieSBlYWNoIHRlYW0gYW5kIGVhY2ggdGVhbXMgZGlzdGFuY2UgZnJvbSByb29tIEEgYW5kIHJvb20gQiwgd2hhdCBpcyB0aGUgbWluaW11bSB0b3RhbCBwb3NzaWJsZSBkaXN0YW5jZSB0aGF0IG11c3QgYmUgdHJhdmVsZWQgYnkgYWxsIGJhbGxvb25zIGFzIHRoZXkgYXJlIGRlbGl2ZXJlZCB0byB0aGVpciByZXNwZWN0aXZlIHRlYW1zLCBhc3N1bWluZyB0aGV5IGFyZSBhbGxvY2F0ZWQgaW4gYW4gb3B0aW1hbCBmYXNoaW9uIGZyb20gcm9vbXMgQSBhbmQgQj8gRm9yIHRoZSBwdXJwb3NlcyBvZiB0aGlzIHByb2JsZW0sIGFzc3VtZSB0aGF0IHRoZSBjb250ZXN0IHN0YWZmIHdlcmUgY2hlYXAgYW5kIG9ubHkgYm91Z2h0IG9uZSBjb2xvciBvZiBiYWxsb29uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGRhdGEgXHVmYjAxbGUuIEVhY2ggdGVzdCBjYXNlIHdpbGwgYmVnaW4gd2l0aCBhIGxpbmUgd2l0aCB0aHJlZSBpbnRlZ2Vyczo8XC9wPlxyXG5cclxuPHByZT5cclxuTiBBIEI8XC9wcmU+XHJcblxyXG48cD53aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgdGVhbXMgKDEgJmxlOyBOICZsZTsgMSwwMDApLCBhbmQgQSBhbmQgQiBhcmUgdGhlIG51bWJlciBvZiBiYWxsb29ucyBpbiByb29tcyBBIGFuZCBCLCByZXNwZWN0aXZlbHkgKDAgJmxlOyBBLCBCICZsZTsgMTAsMDAwKS48XC9wPlxyXG5cclxuPHA+T24gZWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIHRoZXJlIHdpbGwgYmUgdGhyZWUgaW50ZWdlcnMsIHJlcHJlc2VudGluZyBpbmZvcm1hdGlvbiBmb3IgZWFjaCB0ZWFtOjxcL3A+XHJcblxyXG48cHJlPlxyXG5LIEQ8c3ViPkE8XC9zdWI+IEQ8c3ViPkI8XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgSyBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIGJhbGxvb25zIHRoYXQgdGhpcyB0ZWFtIHdpbGwgbmVlZCwgRDxzdWI+QTxcL3N1Yj4gaXMgdGhlIGRpc3RhbmNlIG9mIHRoaXMgdGVhbSBmcm9tIHJvb20gQSwgYW5kIEQ8c3ViPkI8XC9zdWI+IGlzIHRoaXMgdGVhbXMgZGlzdGFuY2UgZnJvbSByb29tIEIgKDAgJmxlOyBEPHN1Yj5BPFwvc3ViPiwgRDxzdWI+QjxcL3N1Yj4mbmJzcDsmbGU7IDEmbmJzcDswMDApLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZXJlIGFyZSBlbm91Z2ggYmFsbG9vbnMgLSB0aGF0IGlzLCAmU2lnbWE7PHN1Yj5pPFwvc3ViPiZuYnNwO0s8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyBBK0IuIFRoZSBkYXRhIFx1ZmIwMWxlIHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggdGhyZWUgMHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciwgcmVwcmVzZW50aW5nIHRoZSBtaW5pbXVtIHRvdGFsIGRpc3RhbmNlIHRoYXQgbXVzdCBiZSB0cmF2ZWxlZCB0byBkZWxpdmVyIGFsbCBvZiB0aGUgYmFsbG9vbnMuIENvdW50IG9ubHkgdGhlIG91dGJvdW5kIHRyaXAsIGZyb20gQSBvciBCIHRvIHRoZSB0ZWFtLiBEb250IGNvdW50IHRoZSBkaXN0YW5jZSB0aGF0IGEgcnVubmVyIG11c3QgdHJhdmVsIHRvIHJldHVybiB0byByb29tIEEgb3Igcm9vbSBCLiBQcmludCBlYWNoIGludGVnZXIgb24gaXRzIG93biBsaW5lIHdpdGggbm8gc3BhY2VzLiBEbyBub3QgcHJpbnQgYW55IGJsYW5rIGxpbmVzIGJldHdlZW4gYW5zd2Vycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=