CF1601E Phys Ed Online

一所不知名大学的学生没有体育课。这就是为什么他们中的 $q$ 个人决定自己去附近的健身房。健身房共开放 $n$ 天，并设有门票系统。在第$i$天，一张门票的费用等于 $a_i$，您被允许每天可以购买若干张门票（可以不买）。 您可以在第 $i$ 天或之后的任何一天激活已购买的门票。每张已激活的门票仅在 $k$ 天内有效。换句话说，如果您在第 $t$ 天激活了门票，它将仅在第 $t,t+1\dots t+k-1$ 天有效。 您现在知道第 $j$ 个学生想要在从 $l_i$ 到 $r_i$ 的每一天都去健身房。而每个学生将在第 $i$ 天 $(l_i \le i \le r_i)$ 通过下列的步骤进入健身房: 1. 一个学生来到健身房门口的售票处，用 $a_i$ 的价格购买几张门票。($a_i$ 可能为零) 2. 如果这个学生至少有一张已激活的有效门票，便可直接进入健身房。否则，这个学生必须激活一张今天或是更早时候购买的门票才能进入健身房。 注意，每个学生从第 $l_j$ 天开始就会去健身房，所以每个学生必须在第 $l_j$ 天购买至少一张门票。 请帮助学生们计算去健身房的最低花费。

第一行包含三个整数 $n,q,k$ ($1 \leqslant n,q \leqslant 300000;1\leqslant k \leqslant n$) 表示有$n$天，$q$个学生，以及每张门票的有效期为$k$天。 第二行包含 $n$ 个整数 $a_1,a_2,...a_n(1 \leqslant a_i \leqslant 10^9)$ 表示相应天数的一张门票的费用。 接下来的 $q$ 行中，每一行都包含两个整数，$l_i$ 和 $r_i$ ($1 \leqslant l_i \leqslant r_i \leqslant n$) 表示相应的学生想去健身房的时间段。

输出每个学生去健身房的最低花费。

让我们看看每个学生如何花钱： - 第一名学生应在第 $1$ 天购买一张门票。 - 第二名学生应在第 $3$ 天购买一张门票，在第 $4$ 天购买两张门票。注意，学生们可以在接下来的几天中保留已购买的门票。 - 第三名学生应在第 $5$ 天购买一张门票。 - 第四名学生应在第 $7$ 天购买一张门票。 - 第五名学生应在第 $3$ 天购买一张门票，第 $4$ 天购买一张门票。