문제
역사와 전통을 자랑하는 제271회 UDPC의 개최를 위해 오늘도 수많은 운영진이 동분서주하고 있다. 운영진인 민호는 이전 대회들과 다르게, 개막식을 관현악 사중주로 시작해서 대회에 참여하는 사람들에게 더 풍성한 경험을 주고자 한다.
사중주는 여러 소리가 동시에 어우러져서 조화를 이루는 것이 중요한 만큼, 민호는 연주회의 조화도가 최대가 되도록 네 명의 학생을 선발해서 자리를 배치하려고 한다. 사중주는 네 명의 학생들이 일렬로 앉아서 연주를 진행하는 형태로 이루어진다.
UNIST, DGIST, POSTECH에는 악기를 잘 다루는 학생들이 다 합해서 $N$명이 있고, 이 중 $M$쌍의 학생들 사이에는 시너지가 존재한다. 어떤 시너지에 포함되는 두 학생이 모두 연주회에 참여하고, 두 학생의 연주 위치가 양옆으로 인접하다면 연주회의 조화도가 $d_i$만큼 상승하게 된다.
민호가 사중주에 참여할 학생들을 고르고 자리를 배치할 수 있는 모든 경우 중, 연주회의 조화도가 최대가 될 때의 그 값을 구해보자.
출력
민호가 사중주에 참여할 네 명의 학생들을 고르고, 자리를 정하는 모든 경우 중에서 연주회의 조화도가 최대가 될 때의 값을 출력한다.
W3sicHJvYmxlbV9pZCI6IjI3OTI2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUXVhcnRldCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWVkXHVjMGFjXHVjNjQwIFx1YzgwNFx1ZDFiNVx1Yzc0NCBcdWM3OTBcdWI3OTFcdWQ1NThcdWIyOTQgXHVjODFjMjcxXHVkNjhjIFVEUENcdWM3NTggXHVhYzFjXHVjZDVjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWM2MjRcdWIyOThcdWIzYzQgXHVjMjE4XHViOWNlXHVjNzQwIFx1YzZiNFx1YzYwMVx1YzljNFx1Yzc3NCBcdWIzZDlcdWJkODRcdWMxMWNcdWM4ZmNcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM2YjRcdWM2MDFcdWM5YzRcdWM3NzggXHViYmZjXHVkNjM4XHViMjk0IFx1Yzc3NFx1YzgwNCBcdWIzMDBcdWQ2OGNcdWI0ZTRcdWFjZmMgXHViMmU0XHViOTc0XHVhYzhjLCBcdWFjMWNcdWI5YzlcdWMyZGRcdWM3NDQgXHVhZDAwXHVkNjA0XHVjNTQ1IFx1YzBhY1x1YzkxMVx1YzhmY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YzVlY1x1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViMzU0IFx1ZDQ4ZFx1YzEzMVx1ZDU1YyBcdWFjYmRcdWQ1ZDhcdWM3NDQgXHVjOGZjXHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjOTExXHVjOGZjXHViMjk0IFx1YzVlY1x1YjdlYyBcdWMxOGNcdWI5YWNcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzViNFx1YzZiMFx1YjdlY1x1YzgzOFx1YzExYyBcdWM4NzBcdWQ2NTRcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViOWNjXHVkMDdjLCBcdWJiZmNcdWQ2MzhcdWIyOTQgXHVjNWYwXHVjOGZjXHVkNjhjXHVjNzU4IDxzdHJvbmc+XHVjODcwXHVkNjU0XHViM2M0PFwvc3Ryb25nPlx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIDxzdHJvbmc+XHViMTI0IFx1YmE4NTxcL3N0cm9uZz5cdWM3NTggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YzEyMFx1YmMxY1x1ZDU3NFx1YzExYyBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGFjXHVjOTExXHVjOGZjXHViMjk0IFx1YjEyNCBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IDxzdHJvbmc+XHVjNzdjXHViODJjXHViODVjPFwvc3Ryb25nPiBcdWM1NDlcdWM1NDRcdWMxMWMgXHVjNWYwXHVjOGZjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5VTklTVCwgREdJU1QsIFBPU1RFQ0hcdWM1ZDBcdWIyOTQgXHVjNTQ1XHVhZTMwXHViOTdjIFx1Yzc5OCBcdWIyZTRcdWI4ZThcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YjJlNCBcdWQ1NjlcdWQ1NzRcdWMxMWMgJE4kXHViYTg1XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzkxMSAkTSRcdWMzMGRcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWMyZGNcdWIxMDhcdWM5YzBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjMmRjXHViMTA4XHVjOWMwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1ZjBcdWM4ZmNcdWQ2OGNcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTU4XHVhY2UwLCBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzVmMFx1YzhmYyBcdWM3MDRcdWNlNThcdWFjMDAgXHVjNTkxXHVjNjA2XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1OFx1YjJlNFx1YmE3NCBcdWM1ZjBcdWM4ZmNcdWQ2OGNcdWM3NTggXHVjODcwXHVkNjU0XHViM2M0XHVhYzAwICRkX2kkXHViOWNjXHVkMDdjIFx1YzBjMVx1YzJiOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmJmY1x1ZDYzOFx1YWMwMCBcdWMwYWNcdWM5MTFcdWM4ZmNcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTYwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWFjZTAgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjAgXHVjOTExLCBcdWM1ZjBcdWM4ZmNcdWQ2OGNcdWM3NTggXHVjODcwXHVkNjU0XHViM2M0XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MjAgXHViNTRjXHVjNzU4IFx1YWRmOCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2YzRcdWJjZjQgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCAkTiRcdWFjZmMgXHVjMmRjXHViMTA4XHVjOWMwXHVjNzU4IFx1YzIxOCAkTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDRcXGxlIE5cXGxlIDIwMFxcIDAwMDswXFxsZSBNXFxsZSAzMDBcXCAwMDApJDxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRNJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzEzOCBcdWM4MTVcdWMyMTggJHVfaSx2X2ksZF9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJHVfaSRcdWJjODggXHVkNTU5XHVjMGRkXHVhY2ZjICR2X2kkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YzVmMFx1YzhmY1x1ZDU1OFx1YmE3NCBcdWM1ZjBcdWM4ZmNcdWQ2OGNcdWM3NTggXHVjODcwXHVkNjU0XHViM2M0XHVhYzAwICRkX2kkXHViOWNjXHVkMDdjIFx1YzBjMVx1YzJiOVx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWI0NTAgXHVkNTU5XHVjMGRkIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyZGNcdWIxMDhcdWM5YzBcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGUgdV9pJmx0O3ZfaVxcbGUgTjsxXFxsZSBkX2lcXGxlIDEwXjkpJDxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmJmY1x1ZDYzOFx1YWMwMCBcdWMwYWNcdWM5MTFcdWM4ZmNcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTYwIFx1YjEyNCBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YWNlMCwgXHVjNzkwXHViOWFjXHViOTdjIFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVjNmIwIFx1YzkxMVx1YzVkMFx1YzExYyBcdWM1ZjBcdWM4ZmNcdWQ2OGNcdWM3NTggXHVjODcwXHVkNjU0XHViM2M0XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MjAgXHViNTRjXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc5MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJRdWFydGV0IiwiZGVzY3JpcHRpb24iOiI8cD5OdW1lcm91cyBzdGFmZiBtZW1iZXJzIGFyZSB3b3JraW5nIGhhcmQgdG9kYXkgZm9yIHRoZSAyNzFzdCBVRFBDLCB3aGljaCBib2FzdHMgYSByaWNoIGhpc3RvcnkgYW5kIHRyYWRpdGlvbi4gT25lIG9mIHRoZSBzdGFmZiBtZW1iZXJzLCBNaW5obywgaXMgcHJlcGFyaW5nIGZvciBhIGRpZmZlcmVudCBvcGVuaW5nIGNlcmVtb255IGNvbXBhcmVkIHRvIHByZXZpb3VzIGNvbXBldGl0aW9ucy4gSGUgcGxhbnMgdG8gc3RhcnQgd2l0aCBhIHN0cmluZyBxdWFydGV0IHBlcmZvcm1hbmNlIHRvIHByb3ZpZGUgYSByaWNoIGV4cGVyaWVuY2UgZm9yIHRoZSBwYXJ0aWNpcGFudHMuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGltcG9ydGFudCBmb3IgYSBxdWFydGV0IHRvIGhhcm1vbml6ZSB2YXJpb3VzIHNvdW5kcy4gTWluaG8gd2FudHMgdG8gc2VsZWN0IDxzdHJvbmc+Zm91cjxcL3N0cm9uZz4gc3R1ZGVudHMgYW5kIGFycmFuZ2Ugc2VhdHMgdG8gbWF4aW1pemUgdGhlIDxzdHJvbmc+aGFybW9ueSBzY29yZTxcL3N0cm9uZz4gb2YgdGhlIGNvbmNlcnQuIFRoZSBxdWFydGV0IGNvbnNpc3RzIG9mIGZvdXIgc3R1ZGVudHMgc2l0dGluZyA8c3Ryb25nPmluIGEgcm93PFwvc3Ryb25nPiBhbmQgcGVyZm9ybWluZy48XC9wPlxyXG5cclxuPHA+VU5JU1QsIERHSVNULCBhbmQgUE9TVEVDSCBoYXZlIGEgdG90YWwgb2YgJE4kIHN0dWRlbnRzIHdobyBhcmUgc2tpbGxlZCBpbiBwbGF5aW5nIG11c2ljYWwgaW5zdHJ1bWVudHMuIEFuZCBhbW9uZyB0aGVtLCBzeW5lcmd5IGV4aXN0cyBiZXR3ZWVuICRNJCBwYWlycyBvZiBzdHVkZW50cy4gSWYgYm90aCBzdHVkZW50cyBpbmNsdWRlZCBpbiBhIHN5bmVyZ3kgcGFydGljaXBhdGUgaW4gdGhlIGNvbmNlcnQsIGFuZCB0aGUgcG9zaXRpb25zIHdoZXJlIHRoZSB0d28gc3R1ZGVudHMgcGxheSBhcmUgYWRqYWNlbnQgdG8gZWFjaCBvdGhlciwgdGhlIGhhcm1vbnkgc2NvcmUgb2YgdGhlIGNvbmNlcnQgaW5jcmVhc2VzIGJ5ICRkX2kkLjxcL3A+XHJcblxyXG48cD5MZXQmIzM5O3MgZmluZCB0aGUgbWF4aW11bSBoYXJtb255IHNjb3JlIG9mIHRoZSBjb25jZXJ0IGFtb25nIGFsbCB0aGUgcG9zc2libGUgY2FzZXMgd2hlcmUgTWluaG8gc2VsZWN0cyBhbmQgYXJyYW5nZXMgdGhlIHN0dWRlbnRzIHdobyB3aWxsIHBhcnRpY2lwYXRlIGluIHRoZSBzdHJpbmcgcXVhcnRldC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kLCZuYnNwOyRNJC4gJCg0XFxsZSBOXFxsZSAyMDBcXCAwMDA7MFxcbGUgTVxcbGUgMzAwXFwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJE0kIGxpbmVzIGNvbnRhaW4gdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzJm5ic3A7JHVfaSx2X2ksZF9pJC4gVGhpcyBtZWFucyB0aGF0IGlmIHN0dWRlbnQgJHVfaSQgYW5kIHN0dWRlbnQgJHZfaSQgcGxheSBpbiBhZGphY2VudCBwb3NpdGlvbnMsIHRoZSBoYXJtb255IHNjb3JlIG9mIHRoZSBjb25jZXJ0IGluY3JlYXNlcyBieSAkZF9pJC4gVGhlcmUgaXMgb25seSBvbmUgc3luZXJneSBiZXR3ZWVuIGFueSB0d28gc3R1ZGVudHMuJm5ic3A7JCgxXFxsZSB1X2kmbHQ7dl9pXFxsZSBOOzFcXGxlIGRfaVxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPkFsbCBnaXZlbiB2YWx1ZXMgYXJlIGludGVnZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBtYXhpbXVtIGhhcm1vbnkgc2NvcmUgb2YgdGhlIGNvbmNlcnQgYW1vbmcgYWxsIHRoZSBwb3NzaWJsZSBjYXNlcyB3aGVyZSBNaW5obyBzZWxlY3RzIGFuZCBhcnJhbmdlcyB0aGUgc3R1ZGVudHMgd2hvIHdpbGwgcGFydGljaXBhdGUgaW4gdGhlIHN0cmluZyBxdWFydGV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=