1031.html

<span style="font-family: Courier New;">จอมยุทธทุกคนก่อนที่จะเป็นยอดฝีมือได้นั้นจะต้องผ่านการฝึกฝนที่หนักหนาสาหัสด้วยกันทั้งสิ้น วิธีหนึ่งในการฝึกฝนตนเองของเหล่ายอดยุทธ คือ การฝ่าด่านต่างๆ ในหอฝึกยุทธ ชาวยุทธแต่ละคนที่ผ่านหอฝึกยุทธมาได้ล้วนกลายเป็นผู้เลื่องชื่อ ยิ่งขึ้นไปบนหอฝึกยุทธได้สูงเท่าไร ก็จะได้ยอดวิชาในระดับที่สูงขึ้นไปเท่านั้น  อย่างไรก็ตามแต่ละคนมีพลังในการฝ่าด่านไม่เท่ากัน ไม่ใช่ว่าใครก็จะสามารถขึ้นไปบนหอชั้นสูงสุดได้<br />
<br />
ในการฝ่าแต่ละด่านผู้ฝึกยุทธจะต้องเสียพลังงานไปหนึ่งหน่วยและต้องฝ่าด่านให้ได้  ก่อนถึงจะไปยังชั้น ต่อไปได้ แต่ละชั้นไม่จำเป็นต้องมีบันไดเชื่อมกับชั้นที่ติดกัน บางชั้นอาจจะไม่มีบันไดเลยในขณะที่บางชั้นอาจจะมีบันไดมากกว่าหนึ่งอันก็ได้ และบันไดทุกอันเป็นบันไดพิเศษที่ขึ้นได้ลงไม่ได้ (ตอนขากลับผู้ฝึกยุทธต้องใช้วิชาตัวเบาร่อนลงมายังชั้นล่างสุด)<br />
<br />
คุณได้รับการว่าจ้างจากผู้ฝึกยุทธนิรนามผู้หนึ่งให้ช่วยหาทางที่จะขึ้นไปยังหอฝึกยุทธให้สูงที่สุดเท่าที่พลังของเขาจะทำได้<br />
<br />
ให้คุณรับข้อมูลของหอฝึกยุทธและพลังของผู้ฝึกยุทธท่านนั้น  แล้วหาว่าเขาสามารถขึ้นไปบนหอได้สูงที่สุดชั้นที่เท่าไรโดยเริ่มนับชั้นล่างสุดเป็นชั้นที่ 1 และไม่มีหอสองชั้นใดที่เชื่อมกันด้วยบันไดมากกว่าหนึ่งอัน<br />
<br />
<center><input src="http://www.programming.in.th/task/img/1031/1031-1.gif" type="image" align="middle" /></center><br />
<br />
<u><strong>งานของคุณ</strong></u><br />
รับตัวตัวเลขจำนวนเต็ม K ซึ่งเป็นพลังของผู้ฝึกยุทธ, ตัวเลขจำนวนเต็ม N ซึ่งเป็นจำนวนชั้น ของหอฝึกยุทธ และ ข้อมูลของบันไดในหอแต่ละชั้น ซึ่งเป็นบันไดขึ้นไปยังหอชั้นถัดไป แล้วแสดงผลลัพธ์เป็นชั้นของหอที่สูงที่สุดที่ผู้ฝึกยุทธสามารถขึ้นไปได้<br />
<u><strong><br />
ข้อมูลนำเข้า</strong></u><br />
<strong>บรรทัดแรก</strong> ประกอบด้วยตัวเลขจำนวนเต็มสามตัว K, N และ M (1 &lt;= K &lt;= N &lt;= 10,000; 1 &lt;= M &lt;= 100,000) แยกจากกันด้วยช่องว่างหนึ่งช่อง แทนพลังของผู้ฝึกยุทธ์  จำนวนชั้นของหอฝึกยุทธ์ และจำนวนบันไดตามลำดับ<strong><br />
ในอีก M บรรทัดต่อมา</strong> ในบรรทัดที่ i+1 จะประกอบด้วยตัวเลขจำนวนเต็มสองตัว a<sub>i </sub> และ b<sub>i </sub>(1 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= N) แทนบันไดที่เชื่อมจากชั้น ที่ a<sub>i</sub> ไปยังชั้น ที่ b<sub>i<br />
<br />
</sub><u><strong>ข้อมูลส่งออก</strong></u><br />
ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัว แทนจำนวนชั้นที่สูงที่สุดที่ชาวยุทธที่มีพลังงาน K สามารถขึ้นไปได้<br />
<br />
<u><strong>ที่มา</strong></u><strong>: Young Thai Online Programming Competition 2008</strong> </span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>2 6 5
<br />1 2
<br />1 3
<br />2 5
<br />3 4
<br />5 6</td>
				<td>5</td>
			</tr></table>