Silver II๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/5567)๋ฌธ์ ์๊ทผ์ด๋ ์์ ์ ๊ฒฐํผ์์ ํ๊ต ๋๊ธฐ ์ค ์์ ์ ์น๊ตฌ์ ์น๊ตฌ์ ์น๊ตฌ๋ฅผ ์ด๋ํ๊ธฐ๋ก ํ๋ค. ์๊ทผ์ด์ ๋๊ธฐ๋ ๋ชจ๋ N๋ช ์ด๊ณ , ์ด ํ์๋ค์ ํ๋ฒ์ ๋ชจ๋ 1๋ถํฐ N๊น์ง์ด๋ค. ์๊ทผ์ด์ ํ๋ฒ์ 1์ด๋ค.์๊ทผ์ด๋ ๋๊ธฐ๋ค์ ์น๊ตฌ ๊ด๊ณ๋ฅผ ๋ชจ๋ ์กฐ์ฌํ ๋ฆฌ์คํธ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ์ด ๋ฆฌ์คํธ๋ฅผ ๋ฐํ์ผ๋ก ๊ฒฐํผ์์ ์ด๋ํ ์ฌ๋์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์๊ทผ์ด์ ๋๊ธฐ์ ์ n (2 ≤ n ≤ 500)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ๋ฆฌ์คํธ์ ๊ธธ์ด m (1 ≤ m ≤ 10000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ ์ค๋ถํฐ m๊ฐ ์ค์๋ ์น๊ตฌ ๊ด๊ณ ai bi๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ ai ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์๊ทผ์ด์ ๊ฒฐํผ์์ ์ด๋ํ๋ ๋๊ธฐ์ ..
