1088 : กิ้งก่า (iguana)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)

    คุณเป็นเจ้าของสวนสัตว์ ที่มีกิ้งก่าชนิดประหลาดหายากนำเข้าอยู่ N ตัว อยู่ใน N กรงที่วางเรียงกัน ถ้าเกิดว่ามีคนเอานิ้วไปจิ้มกิ้งก่าชนิดนี้ มันจะเปลี่ยนสีทันที และอาหารที่มันอยากกินก็จะเปลี่ยนไปตามสีของมันด้วย
    กิ้งก่ามีสีที่เป็นไปได้สามสี คือ แดง เขียว และ น้ำเงิน กิ้งก่าสีแดงจะเปลี่ยนสีเป็นสีเขียวเมื่อถูกจิ้ม สีเขียวจะเปลี่ยนเป็นสีน้ำเงิน และสีน้ำเงินจะเปลี่ยนเป็นสีแดง เริ่มต้นกิ้งก่าทุกตัวเป็นสีแดง
    เนื่องจากมีกิ้งก่าหิวโซตัวหนึ่งคาบกุญแจของคุณไปกิน ทำให้คุณไม่ได้ล็อกกรง เมื่อวานนี้ มีเด็กมือบอน M คนเข้ามา คนที่ i เดินจิ้มกิ้งก่าตั้งแต่ตัวละ A_i ถึงตัวที่ B_i ตัวละหนึ่งครั้ง จนกิ้งก่าเปลี่ยนสีมั่วไปหมด
    และเนื่องจากมีกิ้งก่าตัวหนึ่งป่วนคุณตอนกำลังสั่งอาหาร ทำให้อาหารทั้งหมดที่สั่งมานั้นกลายเป็นอาหารสำหรับกิ้งก่าสีเดียว ซึ่งคุณจะเปลี่ยนก็ไม่ทันแล้ว ถามว่า คุณต้องไปจิ้มกิ้งก่าอย่างน้อยกี่ครั้ง เพื่อให้กิ้งก่าทุกตัวสามารถกินอาหารที่สั่งมาได้


งานของคุณ

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

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

    บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน N, M (1≤N≤100,000,000, 0≤M≤100,000)
    บรรทัดถัดไป M บรรทัด มีจำนวนเต็มบวกสองจำนวน A_i, B_i (1≤Ai≤Bi≤N) เป็นการบอกว่า เด็กมือบอนแต่ละคนจิ้มกิ้งก่าตั้งแต่ตัวไหนถึงตัวไหน
   บรรทัดถัดไป มีตัวหนังสือภาษาอังกฤษหนึ่งตัว R (แดง), G (เขียว) หรือ B (น้ำเงิน) เป็นการบอกว่า อาหารที่สั่งมาสำหรับกิ้งก่าสีอะไร

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

    มีบรรทัดเดียว มีจำนวนเต็ม บอกจำนวนครั้งที่น้อยที่สุดที่ต้องจิ้มกิ้งก่า ที่จะทำให้กิ้งก่าทุกตัวเป็นสีเดียวกับอาหาร

อธิบายข้อมูลน้ำเข้าและส่งออก

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

การให้คะแนน

•     50% ของชุดข้อมูลทดสอบทั้งหมด N≤10,000 และ M≤10,000
•     70% ของชุดข้อมูลทดสอบทั้งหมด N≤100,000,000 และ M≤10,000
•     ทุกชุดข้อมูลทดสอบ N≤100,000,000 และ M≤100,000

โจทย์โดย: ทักษพร กิตติอัครเสถียร
ที่มา: TOI.C:04-2009

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

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