คุณได้เข้าร่วมการแข่งขันเดินทางข้ามประเทศอียิปต์จากทิศตะวันตกไปทิศตะวันออกบนเส้นทางที่เป็นส่วนของเส้นตรง เริ่มต้นคุณอยู่ที่จุดปลายสุดทางทิศตะวันตกของส่วนของเส้นตรง เงื่อนไขของการแข่งขันคือคุณจะต้องเดินทางไปตามส่วนของเส้นตรงนี้ และจะต้องเดินทางไปยังทิศตะวันออกเสมอ

มีเครื่องเคลื่อนย้ายมวลสาร (teleporter) อยู่ N เครื่องบนส่วนของเส้นตรงนี้  เครื่องเคลื่อนย้ายมวลสารเครื่องหนึ่งจะมีสองจุดปลาย (endpoints)  เมื่อคุณไปถึงจุดปลายข้างหนึ่งของเครื่อง คุณจะถูกย้ายตำแหน่งไปยังจุดปลายอีกข้างหนึ่งทันที (สังเกตว่า เครื่องเคลื่อนย้ายมวลสารสามารถย้ายคุณไปในทิศตะวันตกหรือตะวันออกก็ได้ ขึ้นกับว่าคุณไปถึงจุดปลายข้างใด)  หลังจากถูกย้ายตำแหน่งแล้ว คุณจะต้องเดินทางต่อไปในทิศตะวันออกตามส่วนของเส้นตรงเสมอ   คุณไม่สามารถที่จะหลีกเลี่ยงจุดปลายของเครื่องเคลื่อนย้ายมวลสารที่อยู่บนเส้นทางได้  ในแต่ละตำแหน่งจะมีจุดปลายของเครื่องเคลื่อนย้ายมวลสารได้ไม่เกินหนึ่งจุด และจุดปลายของเครื่องเคลื่อนย้ายมวลสารจะต้องอยู่ระหว่างจุดเริ่มต้นและจุดสิ้นสุด (“ระหว่าง” ในที่นี้หมายถึง “strictly between” นั่นคือจะต้องไม่อยู่บนจุดเริ่มต้น และไม่อยู่บนจุดสิ้นสุด)

ทุกครั้งที่คุณถูกเคลื่อนย้าย คุณจะได้คะแนน 1 คะแนน  วัตถุประสงค์ของการแข่งขันคือการทำคะแนนให้ได้มากที่สุดเท่าที่จะทำได้  เพื่อที่จะให้ได้คะแนนมากที่สุด คุณสามารถเพิ่มเครื่องย้ายมวลสารได้อีกไม่เกิน M เครื่องก่อนที่คุณจะเริ่มเดินทาง   คุณสามารถได้คะแนนจากเครื่องเคลื่อนย้ายมวลสารที่เพิ่มเข้าไปด้วย

คุณสามารถกำหนดตำแหน่งของจุดปลายของเครื่องเคลื่อนย้ายมวลสารใหม่เหล่านั้นไว้ที่ตำแหน่งใดก็ได้ (รวมถึงตำแหน่งที่ไม่เป็นจำนวนเต็มด้วย) ตราบเท่าที่ตำแหน่งเหล่านั้นไม่ซ้ำกับตำแหน่งที่มีจุดปลายอยู่เดิม กล่าวคือ ตำแหน่งของจุดปลายของเครื่องเคลื่อนย้ายมวลสารทั้งหมดจะต้องไม่ซ้ำกัน นอกจากนี้จุดปลายจะต้องวางอยู่ระหว่างจุดเริ่มต้นและจุดสิ้นสุด (“ระหว่าง” ในที่นี้หมายถึง “strictly between” นั่นคือจะต้องไม่อยู่บนจุดเริ่มต้น และไม่อยู่บนจุดสิ้นสุด)

สังเกตว่า เราสามารถรับประกันว่า ไม่ว่าคุณจะวางเครื่องเคลื่อนย้ายมวลสารที่ใด  คุณสามารถที่จะไปถึงจุดสิ้นสุดได้เสมอ

โจทย์

จงเขียนโปรแกรมที่รับตำแหน่งของจุดปลายของเครื่องเคลื่อนย้ายมวลสาร N เครื่อง และจำนวนเต็ม M แทนจำนวนเครื่องเคลื่อนย้ายมวลสารที่คุณสามารถเพิ่มได้ จากนั้นคำนวณคะแนนที่มากที่สุดที่คุณสามารถได้รับ

ข้อจำกัด

1 ≤ N ≤ 1,000,000                แทนจำนวนเครื่องเคลื่อนย้ายมวลสารเริ่มต้น

1 ≤ M ≤ 1,000,000               แทนจำนวนเครื่องเคลื่อนย้ายมวลสารที่มากที่สุดที่คุณสามารถเพิ่มได้

1 ≤ W_x < E_x ≤ 2,000,000      แทนระยะทางจากจุดเริ่มต้นของส่วนของเส้นตรง ไปยังจุดปลายด้านตะวันตกและจุดปลายด้านตะวันออกของเครื่องเคลื่อนย้ายมวลสาร x

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

โปรแกรมของคุณจะต้องอ่านข้อมูลเหล่านี้จาก standard input:

บรรทัดที่ 1 ระบุจำนวนเต็ม N  แทนจำนวนของเครื่องเคลื่อนย้ายมวลสารบนส่วนของเส้นตรงที่มีอยู่เดิม

บรรทัดที่ 2 ระบุจำนวนเต็ม M แทนจำนวนเครื่องเคลื่อนย้ายมวลสารที่มากที่สุดที่คุณสามารถเพิ่มได้

N บรรทัดถัดไประบุข้อมูลของเครื่องเคลื่อนย้ายมวลสารแต่ละเครื่อง  กล่าวคือ ในบรรทัดที่ i ของบรรทัดเหล่านี้ ระบุข้อมูลของเครื่องเคลื่อนย้ายมวลสารที่ i  แต่ละบรรทัดประกอบด้วยจำนวนเต็ม 2 จำนวน คือ W_i และ E_i คั่นด้วยช่องว่างหนึ่งช่อง  จำนวน ทั้งสองนี้ระบุระยะทางจากจุดเริ่มต้นของส่วนของเส้นตรงไปยังจุดปลายด้านทิศ ตะวันตกและจุดปลายด้านทิศตะวันออกของเครื่องเคลื่อนย้ายมวลสารนั้น ตามลำดับ

ไม่มีจุดปลายของเครื่องเคลื่อนย้ายมวลสารใด ๆ อยู่บนตำแหน่งเดียวกัน  ส่วนของเส้นตรงที่คุณต้องเดินทางเริ่มที่ตำแหน่ง 0 และสิ้นสุดที่ตำแหน่ง 2,000,001

ข้อมูลส่งออก

โปรแกรมของคุณต้องเขียนผลลัพธ์หนึ่งบรรทัดออกทาง standard output  เป็นจำนวนเต็มหนึ่งจำนวน แทนคะแนนที่มากที่สุดที่คุณสามารถได้รับ

การให้คะแนน

ในข้อมูลชุดทดสอบจำนวน 30 คะแนน  N  ≤ 500 และ M  ≤ 500

ตัวอย่าง

รูปแรกแสดงส่วนของเส้นตรงพร้อมด้วยเครื่องเคลื่อนย้ายมวลสารเริ่มต้นสามเครื่อง  รูปที่สองแสดงส่วนของเส้นตรงเดิมหลังจากเพิ่มเครื่องเคลื่อนย้ายมวลสารหนึ่งเครื่องโดยมีจุดปลายทั้งสองอยู่ที่ตำแหน่ง 0.5 และ 1.5

หลังจากที่เพิ่มเครื่องเคลื่อนย้ายมวลสารใหม่ดังแสดงในรูปข้างต้น การเดินทางของคุณต้องเป็นดังนี้

คุณเริ่มต้นที่ตำแหน่ง 0 และเดินทางไปในทิศตะวันออก

คุณไปถึงยังจุดปลายที่ตำแหน่ง 0.5 และถูกเคลื่อยย้ายไปยังตำแหน่ง 1.5 (คุณได้รับ 1 คะแนน)

คุณเดินทางต่อไปทางทิศตะวันออกจนถึงจุดปลายที่ตำแหน่ง 2  คุณถูกเคลื่อนย้ายไปยังตำแหน่ง 3 (คุณมีคะแนนรวม 2 คะแนน)

คุณเดินทางไปถึงจุดปลายที่ตำแหน่ง 4 และถูกเคลื่อนย้ายไปยังตำแหน่ง 1 (คุณมีคะแนนรวม 3 คะแนน)

คุณไปถึงจุดปลายที่ตำแหน่ง 1.5 ถูกเคลื่อนย้ายไปยังตำแหน่ง 0.5 (คุณมีคะแนนรวม 4 คะแนน)

คุณไปถึงจุดปลายที่ตำแหน่ง 1 ถูกเคลื่อนย้ายไปยังตำแหน่ง 4 (คุณมี 5 คะแนน)

คุณไปถึงจุดปลายที่ตำแหน่ง 10 ถูกเคลื่อนย้ายไปยังตำแหน่ง 11 (คุณมี 6 คะแนน)

คุณเดินทางต่อไปจนกระทั่งไปถึงจุดสิ้นสุด พร้อมด้วยคะแนนรวม 6 คะแนน

ที่มา: 20^th International Olympiad in Informatics; Cairo, Egypt (Day 2)