Grammy มีเพื่อนร่วมทีมสองคนคือ A และ B โดยปกติแล้วเพื่อนร่วมทีมทั้งสองจะออกไปกินข้าวที่ร้านอาหารดีๆ ทุกวัน ในขณะที่ Grammy มักจะกินข้าวที่โรงอาหารของมหาวิทยาลัย การกินที่โรงอาหารช่วยประหยัดเวลาและเงิน ในขณะที่การออกไปกินข้างนอกบางครั้งมีค่าแท็กซี่ ถึงอย่างนั้น ก็มีบางครั้งที่ Grammy เลือกที่จะออกไปกินข้าวกับเพื่อนร่วมทีมเพื่อเพิ่มคุณภาพมื้ออาหารของเธอ
เมื่อใกล้ถึงสิ้นเดือน Grammy เหลือเงินค่าครองชีพเพียง $m$ หยวน และเธอต้องใช้ชีวิตในอีก $n$ วันถัดไปด้วยเงินจำนวนนี้ ในวันที่ $i$ เธอมีสองทางเลือก:
- กินที่โรงอาหาร ได้รับความพึงพอใจ $a_i$ และจ่ายเงิน $b_i$ หยวน
- ออกไปกินข้าวกับเพื่อนร่วมทีม ได้รับความพึงพอใจ $c_i$ และจ่ายเงิน $d_i$ หยวน
เนื่องจาก A และ B ออกไปกินข้าวข้างนอกทุกวัน จึงมีค่าแท็กซี่ในทุกๆ วัน ให้ $e_i$ เป็นค่าแท็กซี่ในวันที่ $i$ ทั้งสามคนได้ตั้งกฎในการจ่ายค่าแท็กซี่ไว้ดังนี้:
- หาก Grammy ไม่ได้ออกไปกินข้าวข้างนอกในวันที่ $i$ จะมีความน่าจะเป็น $\frac{p_i}{100}$ ที่ A จะเป็นคนจ่ายค่าแท็กซี่ และมีความน่าจะเป็น $(1 - \frac{p_i}{100})$ ที่ B จะเป็นคนจ่าย
- หาก Grammy ออกไปกินข้าวข้างนอกในวันที่ $i$ และนับตั้งแต่ครั้งล่าสุดที่ Grammy จ่ายค่าแท็กซี่ (หรือนับตั้งแต่วันแรก หาก Grammy ไม่เคยจ่ายค่าแท็กซี่เลย) ทั้ง A และ B ต่างก็เคยจ่ายค่าแท็กซี่มาแล้วอย่างน้อยคนละหนึ่งครั้ง (ไม่ว่าในตอนนั้น Grammy จะได้ออกไปกินข้าวด้วยหรือไม่ก็ตาม) ครั้งนี้ Grammy จะต้องเป็นคนจ่ายค่าแท็กซี่ มิฉะนั้น เพื่อนร่วมทีมคนใดคนหนึ่งจะเป็นคนจ่ายตามกฎข้อก่อนหน้า
ในแต่ละวัน Grammy จะเลือกการกระทำของเธอก่อนมื้ออาหาร เธอจะทราบว่าใครเป็นคนจ่ายค่าแท็กซี่ในวันก่อนหน้า และเป้าหมายของเธอคือการทำให้ค่าคาดหมายของความพึงพอใจรวมมีค่ามากที่สุด โดยต้องรับประกันว่าค่าใช้จ่ายรวมจะไม่เกิน $m$ หยวนในกรณีที่เลวร้ายที่สุด หากเธอตัดสินใจอย่างเหมาะสมที่สุดในทุกๆ วัน ค่าคาดหมายของความพึงพอใจรวมจะเป็นเท่าใด?
ข้อมูลนำเข้า
ในแต่ละไฟล์ทดสอบมีชุดข้อมูลทดสอบเพียงชุดเดียวเท่านั้น
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n$ และ $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$) แทนจำนวนวันและขีดจำกัดค่าใช้จ่ายรวม
สำหรับอีก $n$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มหกจำนวน $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ และ $p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$) ความหมายของตัวแปรเหล่านี้อธิบายไว้ข้างต้นแล้ว
ข้อมูลส่งออก
แสดงผลหนึ่งบรรทัดที่มีตัวเลขเพียงตัวเดียว แทนค่าคาดหมายสูงสุดของความพึงพอใจรวม หากไม่มีแผนการใดที่ทำให้ค่าใช้จ่ายรวมน้อยกว่าหรือเท่ากับ $m$ หยวนในกรณีที่เลวร้ายที่สุด ให้แสดงผล $-1$
คำตอบของคุณจะถือว่าถูกต้องหากความคลาดเคลื่อนสัมบูรณ์หรือความคลาดเคลื่อนสัมพัทธ์ไม่เกิน $10^{-6}$ กล่าวอย่างเป็นทางการคือ สมมติว่าผลลัพธ์ของคุณคือ $a$ และคำตอบของกรรมการคือ $b$ ผลลัพธ์ของคุณจะได้รับการยอมรับก็ต่อเมื่อ $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$
ตัวอย่าง
2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1