{"raw_statement":[{"iden":"statement","content":"There are _n_ incoming messages for Vasya. The _i_\\-th message is going to be received after _t__i_ minutes. Each message has a cost, which equals to _A_ initially. After being received, the cost of a message decreases by _B_ each minute (it can become negative). Vasya can read any message after receiving it at any moment of time. After reading the message, Vasya's bank account receives the current cost of this message. Initially, Vasya's bank account is at 0.\n\nAlso, each minute Vasya's bank account receives _C_·_k_, where _k_ is the amount of received but unread messages.\n\nVasya's messages are very important to him, and because of that he wants to have all messages read after _T_ minutes.\n\nDetermine the maximum amount of money Vasya's bank account can hold after _T_ minutes."},{"iden":"input","content":"The first line contains five integers _n_, _A_, _B_, _C_ and _T_ (1 ≤ _n_, _A_, _B_, _C_, _T_ ≤ 1000).\n\nThe second string contains _n_ integers _t__i_ (1 ≤ _t__i_ ≤ _T_)."},{"iden":"output","content":"Output one integer — the answer to the problem."},{"iden":"examples","content":"Input\n\n4 5 5 3 5\n1 5 5 4\n\nOutput\n\n20\n\nInput\n\n5 3 1 1 3\n2 2 2 1 1\n\nOutput\n\n15\n\nInput\n\n5 5 3 4 5\n1 2 3 4 5\n\nOutput\n\n35"},{"iden":"note","content":"In the first sample the messages must be read immediately after receiving, Vasya receives _A_ points for each message, _n_·_A_ = 20 in total.\n\nIn the second sample the messages can be read at any integer moment.\n\nIn the third sample messages must be read at the moment T. This way Vasya has 1, 2, 3, 4 and 0 unread messages at the corresponding minutes, he gets 40 points for them. When reading messages, he receives (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5 points. This is 35 in total."}],"translated_statement":[{"iden":"statement","content":"Vasya 收到 #cf_span[n] 条消息。第 #cf_span[i] 条消息将在 #cf_span[ti] 分钟后收到。每条消息的初始成本为 #cf_span[A]。消息被接收后，其成本每分钟减少 #cf_span[B]（可能变为负数）。Vasya 可以在收到消息后的任意时刻阅读该消息，阅读后他的银行账户将获得该消息的当前成本。初始时，Vasya 的银行账户余额为 #cf_span[0]。\n\n此外，每分钟 Vasya 的银行账户会增加 #cf_span[C·k]，其中 #cf_span[k] 是已接收但未读的消息数量。\n\nVasya 非常重视这些消息，因此他希望在 #cf_span[T] 分钟后读完所有消息。\n\n请确定在 #cf_span[T] 分钟后，Vasya 的银行账户最多能有多少资金。\n\n第一行包含五个整数 #cf_span[n], #cf_span[A], #cf_span[B], #cf_span[C] 和 #cf_span[T]（#cf_span[1 ≤ n, A, B, C, T ≤ 1000]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ti]（#cf_span[1 ≤ ti ≤ T]）。\n\n请输出一个整数 —— 问题的答案。\n\n在第一个样例中，消息必须在收到后立即阅读，Vasya 每条消息获得 #cf_span[A] 分，总计 #cf_span[n·A = 20] 分。\n\n在第二个样例中，消息可以在任意整数时刻阅读。\n\n在第三个样例中，消息必须在时刻 #cf_span[T] 阅读。这样，Vasya 在对应分钟分别有 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[4] 和 #cf_span[0] 条未读消息，他因此获得 #cf_span[40] 分。当他阅读消息时，他获得 #cf_span[(5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5] 分，总计 #cf_span[35] 分。"},{"iden":"input","content":"第一行包含五个整数 #cf_span[n], #cf_span[A], #cf_span[B], #cf_span[C] 和 #cf_span[T]（#cf_span[1 ≤ n, A, B, C, T ≤ 1000]）。第二行包含 #cf_span[n] 个整数 #cf_span[ti]（#cf_span[1 ≤ ti ≤ T]）。"},{"iden":"output","content":"输出一个整数 —— 问题的答案。"},{"iden":"examples","content":"输入\n4 5 5 3 5\n1 5 5 4\n输出\n20\n\n输入\n5 3 1 1 3\n2 2 2 1 1\n输出\n15\n\n输入\n5 5 3 4 5\n1 2 3 4 5\n输出\n35"},{"iden":"note","content":"在第一个样例中，消息必须在收到后立即阅读，Vasya 每条消息获得 #cf_span[A] 分，总计 #cf_span[n·A = 20] 分。在第二个样例中，消息可以在任意整数时刻阅读。在第三个样例中，消息必须在时刻 #cf_span[T] 阅读。这样，Vasya 在对应分钟分别有 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[4] 和 #cf_span[0] 条未读消息，他因此获得 #cf_span[40] 分。当他阅读消息时，他获得 #cf_span[(5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5] 分，总计 #cf_span[35] 分。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, A, B, C, T \\in \\mathbb{Z}^+ $ be given parameters.  \nLet $ \\mathbf{t} = (t_1, t_2, \\dots, t_n) \\in \\mathbb{Z}^n $ be the arrival times of the $ n $ messages, where $ 1 \\le t_i \\le T $.  \nLet $ r_i \\in \\{t_i, t_i+1, \\dots, T\\} $ be the time at which message $ i $ is read, for each $ i \\in \\{1, \\dots, n\\} $.\n\n**Constraints**  \n1. $ 1 \\le n, A, B, C, T \\le 1000 $  \n2. $ 1 \\le t_i \\le T $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ t_i \\le r_i \\le T $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nMaximize the total money in Vasya’s bank account at time $ T $, given by:  \n$$\n\\sum_{i=1}^n \\left( A - B \\cdot (r_i - t_i) \\right) + \\sum_{k=1}^T C \\cdot u_k\n$$  \nwhere $ u_k = \\left| \\{ i \\in \\{1, \\dots, n\\} \\mid t_i \\le k < r_i \\} \\right| $ is the number of messages received but not yet read at minute $ k $.\n\nEquivalently, since $ u_k $ counts unread messages at minute $ k $, the second term can be rewritten as:  \n$$\nC \\cdot \\sum_{i=1}^n (r_i - t_i)\n$$  \nbecause each message $ i $ contributes 1 to $ u_k $ for each minute $ k $ from $ t_i $ to $ r_i - 1 $, i.e., for $ r_i - t_i $ minutes.\n\nThus, the total amount is:  \n$$\n\\sum_{i=1}^n \\left( A - B \\cdot (r_i - t_i) \\right) + C \\cdot \\sum_{i=1}^n (r_i - t_i)\n= nA + \\sum_{i=1}^n (C - B)(r_i - t_i)\n$$\n\n**Final Objective**  \nMaximize:  \n$$\nnA + (C - B) \\sum_{i=1}^n (r_i - t_i)\n$$  \nsubject to $ t_i \\le r_i \\le T $ for all $ i $.\n\nSince $ nA $ is constant, the problem reduces to:  \n- If $ C - B > 0 $, maximize $ \\sum_{i=1}^n (r_i - t_i) $ → set $ r_i = T $ for all $ i $.  \n- If $ C - B < 0 $, minimize $ \\sum_{i=1}^n (r_i - t_i) $ → set $ r_i = t_i $ for all $ i $.  \n- If $ C - B = 0 $, the sum is irrelevant → any $ r_i $ yields same result.\n\nThus, the maximum total is:  \n$$\n\\boxed{\nnA + (C - B) \\sum_{i=1}^n \\begin{cases}\nT - t_i & \\text{if } C \\ge B \\\\\n0 & \\text{if } C < B\n\\end{cases}\n}\n$$","simple_statement":null,"has_page_source":false}