A motorcade of n trucks, driving from city «Z» to city «З», has approached a tunnel, known as Tunnel of Horror. Among truck drivers there were rumours about monster DravDe, who hunts for drivers in that tunnel. Some drivers fear to go first, others - to be the last, but let's consider the general case. Each truck is described with four numbers:
Since the road is narrow, it's impossible to escape DravDe, if he appears from one side. Moreover, the motorcade can't be rearranged. The order of the trucks can't be changed, but it's possible to take any truck out of the motorcade, and leave it near the tunnel for an indefinite period. You, as the head of the motorcade, should remove some of the trucks so, that the rest of the motorcade can move into the tunnel and the total amount of the left trucks' values is maximal.
The first input line contains integer number n (1 ≤ n ≤ 10^{5}) — amount of trucks in the motorcade. The following n lines contain four integers each. Numbers in the i-th line: v_{i}, c_{i}, l_{i}, r_{i} (1 ≤ v_{i} ≤ 10^{4}, 1 ≤ c_{i} ≤ 10^{5}, 0 ≤ l_{i}, r_{i} ≤ 10^{5}) — describe the i-th truck. The trucks are numbered from 1, counting from the front of the motorcade.
In the first line output number k — amount of trucks that will drive into the tunnel. In the second line output k numbers — indexes of these trucks in ascending order. Don't forget please that you are not allowed to change the order of trucks. If the answer is not unique, output any.
5
1 1 0 3
1 1 1 2
1 1 2 1
1 1 3 0
2 1 3 0
4
1 2 3 5
5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0
3
1 3 5
Name |
---|