題目背景

由于你的幫助，火星只遭受了最小的損失。但gw懶得重建家園了，就造了一艘飛船飛向遙遠的earth星。不過飛船飛到一半，gw發(fā)現了一個很嚴重的問題：肚子餓了~

gw還是會做飯的，于是拿出了儲藏的食物準備填飽肚子。gw希望能在T時間內做出最美味的食物，但是這些食物美味程度的計算方式比較奇葩，于是絕望的gw只好求助于你了。

題目描述

一共有n件食材，每件食材有三個屬性，ai，bi和ci，如果在t時刻完成第i樣食材則得到ai-t*bi的美味指數，用第i件食材做飯要花去ci的時間。

眾所周知，gw的廚藝不怎么樣，所以他需要你設計烹調方案使得美味指數最大

輸入輸出格式

輸入格式： 第一行是兩個正整數T和n，表示到達地球所需時間和食材個數。

下面一行n個整數，ai

下面一行n個整數，bi

下面一行n個整數，ci

輸出格式： 輸出最大美味指數

輸入輸出樣例

輸入樣例#1： 74 1 502 2 47 輸出樣例#1： 408 說明

【數據范圍】

對于40%的數據1<=n<=10

對于100%的數據1<=n<=50

所有數字均小于100,000

【題目來源】

tinylic改編

分析： 現在考慮相鄰的兩個物品x,y。假設現在已經耗費p的時間，那么分別列出先做x,y的代價：

a[x]-(p+c[x])?$*$b[x]+a[y]-(p+c[x]+c[y])?$*$by

a[y]-(p+c[y])?$*$b[y]+a[x]-(p+c[y]+c[x])?$*$bx

對這兩個式子化簡，得到①＞②的條件是 c[x]?$*$b[y]<$<$c[y]?$*$b[x]. 按這個排序再01背包即可。 注意：DP的數組必須用int64.

代碼：