1031 : Tower
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 128 megabyte(s)
จอมยุทธทุกคนก่อนที่จะเป็นยอดฝีมือได้นั้นจะต้องผ่านการฝึกฝนที่หนักหนาสาหัสด้วยกันทั้งสิ้น วิธีหนึ่งในการฝึกฝนตนเองของเหล่ายอดยุทธ คือ การฝ่าด่านต่างๆ ในหอฝึกยุทธ ชาวยุทธแต่ละคนที่ผ่านหอฝึกยุทธมาได้ล้วนกลายเป็นผู้เลื่องชื่อ ยิ่งขึ้นไปบนหอฝึกยุทธได้สูงเท่าไร ก็จะได้ยอดวิชาในระดับที่สูงขึ้นไปเท่านั้น อย่างไรก็ตามแต่ละคนมีพลังในการฝ่าด่านไม่เท่ากัน ไม่ใช่ว่าใครก็จะสามารถขึ้นไปบนหอชั้นสูงสุดได้

ในการฝ่าแต่ละด่านผู้ฝึกยุทธจะต้องเสียพลังงานไปหนึ่งหน่วยและต้องฝ่าด่านให้ได้ ก่อนถึงจะไปยังชั้น ต่อไปได้ แต่ละชั้นไม่จำเป็นต้องมีบันไดเชื่อมกับชั้นที่ติดกัน บางชั้นอาจจะไม่มีบันไดเลยในขณะที่บางชั้นอาจจะมีบันไดมากกว่าหนึ่งอันก็ได้ และบันไดทุกอันเป็นบันไดพิเศษที่ขึ้นได้ลงไม่ได้ (ตอนขากลับผู้ฝึกยุทธต้องใช้วิชาตัวเบาร่อนลงมายังชั้นล่างสุด)

คุณได้รับการว่าจ้างจากผู้ฝึกยุทธนิรนามผู้หนึ่งให้ช่วยหาทางที่จะขึ้นไปยังหอฝึกยุทธให้สูงที่สุดเท่าที่พลังของเขาจะทำได้

ให้คุณรับข้อมูลของหอฝึกยุทธและพลังของผู้ฝึกยุทธท่านนั้น แล้วหาว่าเขาสามารถขึ้นไปบนหอได้สูงที่สุดชั้นที่เท่าไรโดยเริ่มนับชั้นล่างสุดเป็นชั้นที่ 1 และไม่มีหอสองชั้นใดที่เชื่อมกันด้วยบันไดมากกว่าหนึ่งอัน



งานของคุณ
รับตัวตัวเลขจำนวนเต็ม K ซึ่งเป็นพลังของผู้ฝึกยุทธ, ตัวเลขจำนวนเต็ม N ซึ่งเป็นจำนวนชั้น ของหอฝึกยุทธ และ ข้อมูลของบันไดในหอแต่ละชั้น ซึ่งเป็นบันไดขึ้นไปยังหอชั้นถัดไป แล้วแสดงผลลัพธ์เป็นชั้นของหอที่สูงที่สุดที่ผู้ฝึกยุทธสามารถขึ้นไปได้

ข้อมูลนำเข้า

บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มสามตัว K, N และ M (1 <= K <= N <= 10,000; 1 <= M <= 100,000) แยกจากกันด้วยช่องว่างหนึ่งช่อง แทนพลังของผู้ฝึกยุทธ์ จำนวนชั้นของหอฝึกยุทธ์ และจำนวนบันไดตามลำดับ
ในอีก M บรรทัดต่อมา
ในบรรทัดที่ i+1 จะประกอบด้วยตัวเลขจำนวนเต็มสองตัว ai และ bi (1 <= ai < bi <= N) แทนบันไดที่เชื่อมจากชั้น ที่ ai ไปยังชั้น ที่ bi

ข้อมูลส่งออก
ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งตัว แทนจำนวนชั้นที่สูงที่สุดที่ชาวยุทธที่มีพลังงาน K สามารถขึ้นไปได้

ที่มา: Young Thai Online Programming Competition 2008

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
2 6 5
1 2
1 3
2 5
3 4
5 6
5

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 3 สมาชิก (0 บอท)