3102: 地精的贸易
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：5
题目描述
聪明的地精发现，联盟与部落的市场上的某些商品存在着很大的差价。这决定了地精可以 从中获取相当可观的利润。然而这个发现还并没有被大部分地精知道，于是年轻的地精菲利克 斯决定从事此业。菲利克斯几乎花光了他所有的积蓄购买了一个相当大的飞艇，以及往返于暴 风城和银月城之间的各种通行证。暴风城和银月城分别是联盟和部落的商业中心。菲利克斯决 定在暴风城购买一些商品，驾驶飞艇到银月城以当地市场价卖掉，然后在银月城买一些商品， 驾驶飞艇再回到暴风城卖掉。这样一个来回，菲利克斯可以赚到不少钱。 通过商业调查，他已经在出发前就知道了联盟和部落的各种商品的价格。在他现有的资产 的前提下，他希望能够在一次旅行中赚取尽可能多的金币。那么请你设计一个程序，为菲利克 斯设计一个购买方案，使一次来回能够赚到最多的金币。
输入
第一行，两个整数 N 和 M，表示他在出发前有 N 个金币，联盟和部落的市场中都有 M 种 商品。 第二到 M+1 行，每行两个整数 Ai 和 Bi，表示第 i 种商品在暴风城的市场价为 Ai，在银月 城的市场价为 Bi。
输出
第一行，一个整数，菲利克斯一次来回最多能够赚到的金币数。 第二到 M+1 行，第 i+1 行为第 i 个商品的购买方法，输出一个句子。如果要从联盟购买 k 个，输出“Buy k from Aliance”，如果要从部落购买 k 个，输出“Buy k from Horde”，如 果不需要购买，输出“Buy 0”。如果多个的方案赚得的金币都是最大，则输出购买的商品序 号最靠前的这种方案。
样例输入 复制
23 5
6 9
11 7
3 2
4 6
5 3
样例输出 复制
33
Buy 3 from Aliance
Buy 1 from Horde
Buy 0
Buy 1 from Aliance
Buy 9 from Horde提示
初始时，菲利克斯在暴风城，他有 23 个金币，这时他购买 3 个商品 1，1 个商品 4，花 费 3×6+1×4=2 个金币，剩余 1 个金币。到达银月城，他把它们卖掉，可以获得 3×9+1×6=3 个金币，赚了 1 个金币。这时，他用他的 34 个金币，在银月城购买 1 个商 品 2，9 个商品 5，花费 1×7+9×3=34 个金币。回到暴风城，卖掉可以获得 1×1+9×5=56 个金币，赚了 2 个金币。与起始时他的 23 个金币相比，他赚了 3 个金 币。 【数据规模与约定】 对于 10%的数据，1≤N≤105，1≤M≤102 ,答案不超过 4×10^6。