Masala #BPRYGNOE5A

Robolandiya 1 dan N gacha ketma-ket raqamlangan shaharlardan iborat robotlar “uyi”, ya'ni har bir shahar robot ishlab chiqarish bilan shug'ullananadi. Har bir shahar xaridor talabiga ko'ra robotlar uchun narxni o'zi belgilaydi. Yaqin kunlarda uzoq o'lkalardan mehmonlar tashrif buyuradi. Har bir xaridor $[l, r]$ oralig'idagi shaharlarni aylanadi va ushbu shaharlar ichidagi eng arzon narxdagi robotni, agar puli yetsa xarid qiladi. Aks holda hech narsa xarid qilmaydi. Xaridorlar ko'pligi uchun shaharlar robot  narxini belgilashda sizdan yordam so'ramoqda. Robolandiya oladigan foyda maksimal bo'ladigan narxlarni aniqlang.

Birinchi qatorda $N$ va $M$  - shaharlar va turistlar soni kiritiladi.

Keyingi $M$ ta qatorning har birida uchtadan son $a_i, b_i, c_i$ - har bir turist sayohatni qayerdan boshlashi, qaysi shaharda tugatishi va byudjet miqdori kiritiladi. 

$1 \le N \le 50$

$1 \le M \le 4000$

$1 \le a_i \le b_i \le N$

$1 \le c_i \le 5 \times 10^5$

Birinchi qatorda maksimal foyda qiymatini chop eting.

Keyingi qatorda har bir shahar uchun optimal narxni chop eting. Maksimal summani bir necha xil usulda olish mumkin bo'lsa istalganini chop etishingiz mumkin. Har bir shahar uchun narx $[1, 500000]$ oralig'ida bo'lishi zarur.