小藍(lán)很喜歡吃巧克力，他每天都要吃一塊巧克力。 一天小藍(lán)到超市想買一些巧克力。超市的貨架上有很多種巧克力，每種巧克力有自己的價(jià)格、數(shù)量和剩余的保質(zhì)期天數(shù)，小藍(lán)只吃沒過保質(zhì)期的巧克力，請(qǐng)問小藍(lán)最少花多少錢能買到讓自己吃 x 天的巧克力。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) x, n，分別表示需要吃巧克力的天數(shù)和巧克力的種類數(shù)。 接下來 n 行描述貨架上的巧克力，其中第 i 行包含三個(gè)整數(shù) ai, bi, ci，表示第 i 種巧克力的單價(jià)為 ai，保質(zhì)期還剩 bi 天（從現(xiàn)在開始的 bi 天可以吃），數(shù)量為 ci。
輸出格式
輸出一個(gè)整數(shù)表示小藍(lán)的最小花費(fèi)。如果不存在讓小藍(lán)吃 x 天的購買方案，輸出? 1。