题意翻译

有个数，个操作。形如：

1. 将改为
2. 将加上
3. 将乘以

其中第个操作的编号为. 现在你可以从中选择最多个操作(不能重复选),并按一定顺序执行，使得最大。

请输出最后的最大值以及你选择的操作。

输入格式

第一行包含个整数， , ,

第二行包含个整数，表示初始序列。

之后行每行三个整数。分别表示操作类型，要修改的数的下标，修改后的数。

输出格式

输出共两行，第一行包含一个整数，表示最大值。

第二行包含个整数，按顺序输出您选择的操作。

Input & Output 's examples

Input 's eg

2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2

Output 's eg

3
2 3 4

数据范围和约定

对于的数据，保证 , 。

其他的数字均保证在范围内。

分析

一道有点毒瘤的贪心题。

先考虑如果只有操作该怎么做。很显然，若只有操作的话我们直接排个序即可。

既然这样，我们就把前两种操作转换为操作。

对于操作，我们很容易发现对于一个位置，我们最多只会使用一次操作，而且一定是把它改成一个比它大的数。

因此我们可以把这次赋值操作看做一次加法操作。即将操作改成操作。

再来思考如何把操作转变为操作。

不难得出，对于一个数一定是要先加在乘的。而且一定先从大的开始使用。

所以说，每个数进行加法操作的顺序是固定的。把这些加法操作排序后都可以看做乘法操作（）

现在我们只剩下操作了。排个序输出就可以啦。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

struct Change{//opt为操作类型，id为操作编号，a为被修改数的下标，b为被修改后的分子，c为分母
    ll opt , id , a , b , c;    
}node1[N] , node2[N] , node3[N] , ans[N];

ll num1 , num2 , num3;  //记录三种操作的数量

I bool cmp1(Change A , Change B){
    return (A.a != B.a) ? A.a < B.a : A.b < B.b;
}

I bool cmp2(Change A , Change B){
    return (A.a != B.a) ? A.a < B.a : A.b > B.b;
}

I bool cmp3(Change A , Change B){
    return A.b * B.c > A.c * B.b;
}

I bool cmp4(Change A , Change B){
    return A.opt < B.opt;
}

ll n , m , s;
ll a[N];

int main(){
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    int x , y , z;
    for(int i = 1; i <= m; i ++){
        cin >> z >> x >> y;
        if(z == 1 && y > a[x]){     //如果将一个数改成比他小的数，还不如不改。
            node1[++ num1] = (Change){1 , i , x , y , 1};
        }
        else if(z == 2){
            node2[++ num2] = (Change){2 , i , x , y , 1};
        }
        else if(z == 3){
            node3[++ num3] = (Change){3 , i , x , y , 1};
        }

    }
    sort(node1 + 1 , node1 + 1 + num1 , cmp1);  //将操作1排一遍序
    int tmp = 0;
    for(int i = 1; i <= num1; i ++){
        if(node1[i].a != node1[i + 1].a){   //对于每一个位置选出最大的数
            node1[++ tmp] = node1[i];
        }
    }
    num1 = tmp;
    for(int i = 1; i <= num1; i ++){    //将操作1改为操作2
        node2[++ num2].opt = node1[i].opt;
        node2[num2].id = node1[i].id;
        node2[num2].a = node1[i].a;
        node2[num2].b = node1[i].b - a[node1[i].a];
    }
    sort(node2 + 1 , node2 + 1 + num2 , cmp2);  
    ll sum = 0;
    for(int i = 1; i <= num2; i ++) {
        if(node2[i].a != node2[i - 1].a){
            sum = a[node2[i].a];
        }
        node2[i].c = sum, sum += node2[i].b;
    }  
    for(int i = 1; i <= num3; i ++){
        node3[i].b -= 1;
    }
    for(int i = 1; i <= num2; i ++){
        node3[++ num3] = node2[i];  //将操作2改成操作3
    }
    sort(node3 + 1 , node3 + 1 + num3 , cmp3);  
    ll number = min(num3 , s);  //如果可以用的操作数大于总操作数，就都用上。
    int cnt = 0;
    for(int i = 1; i <= number; i ++){
        ans[++ cnt] = node3[i]; 
    }
    cout << cnt << "\n";
    sort(ans + 1 , ans + 1 + cnt , cmp4);
    for(int i = 1; i <= cnt; i ++){
        cout << ans[i].id << " ";
    }
    return 0;
}

THE END