題目描述：

               一個歌手準備從A城去B城參加演出。

              1) 按照合同，他必須在T天內趕到。

              3) 歌手不能往回走。

              4) 每兩座城市之間需要的天數都可以提前獲知。

              5) 歌手在每座城市都可以在路邊賣唱賺錢。經過調研，歌手提前獲知了每座城市賣唱的收入預期：如果在一座城市第一天賣唱可以賺M，后續每天的收入會減少D（第二天賺的錢是M – D，第三天是M-2D…）。如果收入減到0就不會再少了。 

              6) 歌手到達后的第二天才能開始賣唱。如果今天賣過唱，第二天才能出發。

              貪心的歌手最多可以賺多少錢？

輸入描述：第一行兩個數字 T和N，中間用空格隔開。

                  T代表總天數；

                  N代表路上經過N座城市；

                 0 < T < 1000, 0 < N < 100

                 第二行N+1個數字，中間用空格隔開。

                 代表每兩座城市之間耗費的時間。

                 其總和<=T。

                 接下來N行，每行兩個數字M和D，中間用空格隔開。

                 代表每個城市的收入預期。

                 0