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

จากการสำรวจพื้นที่พบว่ามีสิ่งกีดขวางอยู่ P ก้อนซึ่งอาจซ้อนทับกัน แทนด้วยสี่เหลี่ยมในตารางซึ่งด้านทุกด้านขนานกับเส้นในตาราง พื้นที่ที่จะใช้เป็นฐานปิรามิดได้นั้นต้องปราศจากสิ่งกีดขวางใด ๆ   โดยการทำลายสิ่งกีดขวางก้อนที่ i ต้องใช้ค่าใช้จ่าย C_i และการทำลายสิ่งกีดขวางก้อนใดจะต้องทำลายทั้งก้อน นั่นหมายความว่าคุณไม่สามารถทำลายสิ่งกีดขวางใดเพียงบางส่วนได้ ขอให้ทราบว่าการทำลายสิ่งกีดขวางที่ทับซ้อนกับก้อนอื่นจะไม่มีผลต่อสิ่งกีดขวางก้อนอื่น ๆ เหล่านั้น

โจทย์

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

เงื่อนไขและการให้คะแนน

โปรแกรมของคุณจะถูกตรวจด้วยชุดทดสอบสามชุดที่แยกจากกัน ในทุกชุดทดสอบจะมีเงื่อนไขต่อไปนี้

1 ≤ M, N ≤ 1,000,000             ขนาดของตาราง

1 ≤ C_i ≤ 7,000                          ค่าใช้จ่ายในการทำลายสิ่งกีดขวางก้อนที่ i

1 ≤ X_i1 ≤ X_i2 ≤ M                      พิกัดในแกน X ของช่องซ้ายสุดและขวาสุดของสิ่งกีดขวางที่ i ตามลำดับ

1 ≤ Y_i1 ≤ Y_i2 ≤ N                       พิกัดในแกน Y ของช่องล่างสุดและบนสุดของสิ่งกีดขวางที่ i ตามลำดับ

ชุดทดสอบชุดแรก คะแนนรวม 35 คะแนน

B = 0                                       งบประมาณที่มี (นั่นคือคุณไม่มีงบที่จะทำลายสิ่งกีดขวางก้อนใดได้เลย)

1 ≤ P ≤ 1,000                           จำนวนก้อนของสิ่งกีดขวางในตาราง

ชุดทดสอบที่สอง คะแนนรวม 35 คะแนน

0 < B ≤ 2,000,000,000          งบประมาณที่มี

1 ≤ P ≤ 30,000                        จำนวนก้อนของสิ่งกีดขวางในตาราง

ชุดทดสอบที่สาม คะแนนรวม 30 คะแนน

B = 0                                       งบประมาณที่มี (นั่นคือคุณไม่มีงบที่จะทำลายสิ่งกีดขวางก้อนใดได้เลย)

1 ≤ P ≤ 400,000                      จำนวนก้อนของสิ่งกีดขวางในตาราง

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

โปรแกรมต้องอ่านข้อมูลจาก standard input ดังนี้

·        บรรทัดที่ 1 ประกอบด้วยจำนวนเต็มสองตัวคั่นด้วยช่องว่างหนึ่งช่อง ซึ่งก็คือ M และ N ตามลำดับ

·        บรรทัดที่ 2 ประกอบด้วยจำนวนเต็ม B แทนงบประมาณที่มี

·        บรรทัดที่ 3 ประกอบด้วยจำนวนเต็ม P แทนจำนวนสิ่งกีดขวางที่พบในการสำรวจ

·    P บรรทัดถัดมา แต่ละบรรทัดอธิบายรายละเอียดของสิ่งกีดขวางแต่ละก้อน โดยบรรทัดที่ i ของข้อมูลชุดนี้อธิบายสิ่งกีดขวางก้อนที่ i ภายในบรรทัดประกอบด้วยจำนวนเต็ม 5 จำนวนคั่นด้วยช่องว่างหนึ่งช่องคือ X_i1, Y_i1, X_i2, Y_i2, และ C_i ซึ่งแทนพิกัดช่องล่างซ้ายของสิ่งกีดขวาง พิกัดช่องบนขวาของสิ่งกีดขวาง และค่าใช้จ่ายในการทำลายสิ่งกีดขวางนั้น ๆ ตามลำดับ พิกัดของช่องล่างซ้ายสุดของพื้นที่คือ (1,1) และพิกัดของช่องบนขวาสุดของพื้นที่คือ (M,N)

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

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

อธิบายตัวอย่างที่หนึ่ง (ด้านล่าง)

รูปด้านบนแสดงตำแหน่งฐานปิรามิดที่เป็นไปได้สองตำแหน่ง ทั้งคู่ต่างก็มีความยาวด้านเท่ากับ 4

อธิบายตัวอย่างที่สอง (ด้านล่าง)

รูปด้านบนแสดงตำแหน่งที่เป็นไปได้เพียงตำแหน่งเดียว โดยมีความยาวด้านเท่ากับ 3