1036 : Equipped
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
แดงเตรียมตัวไปตั้งแค้มป์ในป่าเขาดงดิบกับเพื่อนๆ เขาไปเดินเลือกซื้ออุปกรณ์ที่ห้างสรรพสินค้าโชว์ห่วย ในร้านมีอุปกรณ์ตั้งแค้มป์ n ชิ้น ผลิตภัณฑ์ชิ้นที่ i มีราคา wi บาท

แดงต้องการอุปกรณ์เหล่านี้ เพื่อใช้งานหลายอย่าง เช่น เหลาไม้ ขุดดิน ฟังเพลง เลื่อยไม้ กรองน้ำ ถลุงเหล็ก โม่แป้ง เป็นต้น รวมการใช้งานทั้งหมดมีได้ k แบบ

แดงมีข้อมูลว่าอุปกรณ์แต่ละชิ้นทำอะไรได้บ้าง โดยสำหรับอุปกรณ์ที่ i และการใช้งานที่ j ค่า p(i,j) จะระบุว่า อุปกรณ์ดังกล่าวมีความสามารถใชงานสำหรับงานที่ j หรือไม่ กล่าวคือ p(i,j) = 1 เมื่ออุปกรณ์ที่ i สามารถทำงาน j ได้ และ p(i,j) = 0 เมื่ออุปกรณ์ชิ้นที่ i ทำไม่ได้

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

ข้อมูลป้อนเข้า
บรรทัดแรกมีจำนวนเต็ม n และ k (1 <= n <= 10 000; 1 <= k <= 8) จากนั้น ในบรรทัดที่ 1+i จะมีจำนวนเต็ม k+1 จำนวนเรียงตามลำดับดังนี้ wi p(i,1) p(i,2) . . . p(i,k)

ข้อมูลส่งออก
มีหนึ่งบรรทัด เป็นจำนวนเงินที่น้อยที่สุดที่สามารถซื้อของที่ทำงานได้ครบทุกอย่าง

ที่มา: อ.ดร.จิตร์ทัศน์ ฝักเจริญผล

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 3
10 1 0 1
30 0 1 1
5 1 0 0
4 0 0 1
150 1 1 1
 35

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

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