๋ฌธ์ N(1 ≤ N ≤ 100,000)๊ฐ์ ๋กํ๊ฐ ์๋ค. ์ด ๋กํ๋ฅผ ์ด์ฉํ์ฌ ์ด๋ฐ์ ๋ฐ ๋ฌผ์ฒด๋ฅผ ๋ค์ด ์ฌ๋ฆด ์ ์๋ค. ๊ฐ๊ฐ์ ๋กํ๋ ๊ทธ ๊ตต๊ธฐ๋ ๊ธธ์ด๊ฐ ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ ๋ค ์ ์๋ ๋ฌผ์ฒด์ ์ค๋์ด ์๋ก ๋ค๋ฅผ ์๋ ์๋ค. ํ์ง๋ง ์ฌ๋ฌ ๊ฐ์ ๋กํ๋ฅผ ๋ณ๋ ฌ๋ก ์ฐ๊ฒฐํ๋ฉด ๊ฐ๊ฐ์ ๋กํ์ ๊ฑธ๋ฆฌ๋ ์ค๋์ ๋๋ ์ ์๋ค. k๊ฐ์ ๋กํ๋ฅผ ์ฌ์ฉํ์ฌ ์ค๋์ด w์ธ ๋ฌผ์ฒด๋ฅผ ๋ค์ด ์ฌ๋ฆด ๋, ๊ฐ๊ฐ์ ๋กํ์๋ ๋ชจ๋ ๊ณ ๋ฅด๊ฒ w/k ๋งํผ์ ์ค๋์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค. ๊ฐ ๋กํ๋ค์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ์ด ๋กํ๋ค์ ์ด์ฉํ์ฌ ๋ค์ด์ฌ๋ฆด ์ ์๋ ๋ฌผ์ฒด์ ์ต๋ ์ค๋์ ๊ตฌํด๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ชจ๋ ๋กํ๋ฅผ ์ฌ์ฉํด์ผ ํ ํ์๋ ์์ผ๋ฉฐ, ์์๋ก ๋ช ๊ฐ์ ๋กํ๋ฅผ ๊ณจ๋ผ์ ์ฌ์ฉํด๋ ๋๋ค. ์ฒซ์งธ ์ค์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ๊ฐ ๋กํ๊ฐ ๋ฒํธ ์ ์..