← 返回题目列表

Codeforces · 28/D

D. 别害怕,DravDe 很友善

中文机器翻译题面 查看原题

一支由 n 辆卡车组成的车队,从城市《Z》行驶到城市《З》,已经接近一条被称为恐怖隧道的隧道。在卡车司机中流传着关于怪物 DravDe 的谣言,它会在隧道里追捕司机。有些司机害怕先走,有些则害怕最后一个,但让我们考虑一下一般情况。每辆卡车都用四个数字进行描述:

- v — 卡车、其乘客和货物的价值
- c — 卡车上的乘客数量,包括司机
- l — 应该在这辆卡车之前进入隧道的总人数,以便司机克服恐惧(“如果怪物出现在车队前面,他会先吃掉他们”)
- r — 应该跟随这辆卡车的总人数,以便司机能够克服他的恐惧(“如果怪物出现在车队后面,他会先吃掉他们”)。

由于道路狭窄,如果 DravDe 从一侧出现,就不可能逃脱。而且,车队无法重新安排。卡车的顺序无法更改,但可以将任何卡车从车队中取出,并将其无限期地留在隧道附近。作为车队的负责人,您应该移除一些卡车,以便车队的其余部分可以进入隧道,并且左侧卡车的总价值最大。

输入

第一输入行包含整数 n (1 ≤ n ≤ 105) — 车队中的卡车数量。接下来的 n 行每行包含四个整数。第 i 行中的数字:vi, ci, li, ri (1 ≤ vi ≤ 104, 1 ≤ ci ≤ 105, 0 ≤ li, ri ≤ 105) — 描述第 i 辆卡车。卡车编号从 1 开始,从车队前面开始数。

输出

在第一行中输出数字 k — 将驶入隧道的卡车数量。在第二行中输出 k 个数字 — 这些卡车的索引,按升序排列。请不要忘记,您不得更改卡车的顺序。如果答案不唯一,则输出任意一个。

示例

输入 #1

5
1 1 0 3
1 1 1 2
1 1 2 1
1 1 3 0
2 1 3 0

输出 #1

4
1 2 3 5

输入 #2

5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0

输出 #2

3
1 3 5