小藍(lán)所在學(xué)校周邊新開業(yè)了一家游樂園，小藍(lán)作為班長，打算組織大家去游樂園玩。已知一共有 N 個(gè)人參加這次活動，游樂園有 M 個(gè)娛樂項(xiàng)目，每個(gè)項(xiàng)目都需要買門票后才可進(jìn)去游玩。門票的價(jià)格并不是固定的，團(tuán)購的人越多單價(jià)越便宜，當(dāng)團(tuán)購的人數(shù)大于某個(gè)閾值時(shí)，這些團(tuán)購的人便可以免費(fèi)進(jìn)入項(xiàng)目進(jìn)行游玩。這 M 個(gè)娛樂項(xiàng)目是獨(dú)立的，所以只有選擇了同一個(gè)項(xiàng)目的人才可

以參與這個(gè)項(xiàng)目的團(tuán)購。第 i 個(gè)項(xiàng)目的門票價(jià)格 Hi 與團(tuán)購的人數(shù) X 的關(guān)系可以看作是一個(gè)函數(shù)：

Hi(X) = max (Ki × X + Bi , 0)

max 表示取二者之中的最大值。當(dāng) Hi = 0 時(shí)說明團(tuán)購人數(shù)達(dá)到了此項(xiàng)目的免單閾值。

這 N 個(gè)人可以根據(jù)自己的喜好選擇 M 個(gè)娛樂項(xiàng)目中的一種，或者有些人對這些娛樂項(xiàng)目都沒有興趣，也可以選擇不去任何一個(gè)項(xiàng)目。每個(gè)人最多只會選擇一個(gè)娛樂項(xiàng)目，如果多個(gè)人選擇了同一個(gè)娛樂項(xiàng)目，那么他們都將享受對應(yīng)的團(tuán)購價(jià)格。小藍(lán)想知道他至少需要準(zhǔn)備多少錢，使得無論大家如何選擇，他都有能力支付得起所有 N 個(gè)人購買娛樂項(xiàng)目的門票錢。

第一行兩個(gè)整數(shù) N、M，分別表示參加活動的人數(shù)和娛樂項(xiàng)目的個(gè)數(shù)。

接下來 M 行，每行兩個(gè)整數(shù)，其中第 i 行為 Ki、Bi，表示第 i 個(gè)游樂地點(diǎn)的門票函數(shù)中的參數(shù)。

一個(gè)整數(shù)，表示小藍(lán)至少需要準(zhǔn)備多少錢，使得大家無論如何選擇項(xiàng)目，自己都支付得起。

其中當(dāng) a = 1, b = 2 時(shí)花費(fèi)最大，為 12。此時(shí) 1 個(gè)人去第一個(gè)項(xiàng)目，所以第一個(gè)項(xiàng)目的單價(jià)為 10 ? 4 = 6，在這個(gè)項(xiàng)目上的花費(fèi)為 6 × 1 = 6；2 個(gè)人去第二個(gè)項(xiàng)目，所以第二個(gè)項(xiàng)目得單價(jià)為 7 ? 2 × 2 = 3，在這個(gè)項(xiàng)目上的花費(fèi)為2 × 3 = 6；還有 1 個(gè)人沒去任何項(xiàng)目，不用統(tǒng)計(jì)；總花費(fèi)為 12，這是花費(fèi)最大的一種方案，所以答案為 12。

對于 30% 的評測用例，1 ≤ N, M ≤ 10。

對于 50% 的評測用例，1 ≤ N, M ≤ 1000。

對于 100% 的評測用例，1 ≤ N, M, B_i ≤ 10⁵，?10⁵ ≤ K_i < 0。