PROGRAMING PROBLEMS

Дархан хотод үйл ажиллагаагаа явуулдаг ХАТАН нэртэй банк өргөжин тэлсээр n ширхэг салбартай болов. Банкны удирдлагууд зарим салбаруудыг хооронд нь хоёр урсгалтай хурдны замаар холбон үйлчилгээгээ хурдасгах ажлыг эхлүүлсэн ба нийт гарах зардлын хэмжээг олох хэрэгтэй болж таниас тусламж гуйжээ. Банкны i, j –р салбарууд хоорондоо ижил зайтай ба тэдгээрийг хооронд нь холбоход k төгрөг зарцуулдаг бол нийт хичнээн төгрөг зарцуулах вэ?

Input

Эхний мөрөнд нийт салбарын тоо n(n<20000) ба i, j –ээр салбарыг холбоход шаардах мөнгөний хэмжээ k(0<=k<=10^7) болох бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн n-1 мөрөнд салбаруудыг холбосон эсэхийг илэрхийлэх холболтын матриц өгөгдөнө.

Output

Нийт хичнээн төгрөг зарцуулахыг ол.

Example

Input:
4 300000
0 0 1 1
0 0 1 0
1 1 0 0
1 0 0 0

Output:
900000