Centre for Gifted Education - Hanoi university of Technology

Có n công việc đánh số từ 1 đến n và một máy để thực hiện chúng. Biết:

• P_i là thời gian cần thiết để hoàn thành công việc i.
• D_i là thời hạn hoàn thành công việc i.

Máy bắt đầu hoạt động từ thời điểm 0. Mỗi công việc cần được thực hiện liên tục từ lúc bắt đầu cho tới khi kết thúc, không cho phép ngắt quãng. Giả sử c_i là thời điểm hoàn thành công việc i. Khi đó, nếu c_i > d_i ta nói công việc i bị hoàn thành trễ hạn, còn nếu c_i ≤ d_i thì ta nói công việc i được hoàn thành đúng hạn.

Yêu cầu: Tìm trình tự thực hiện các công việc sao cho số công việc hoàn thành trễ hạn là ít nhất.

Tham khảo thuật toán More

Input

• Dòng đầu tiên chứa số nguyên dương n (0 < n ≤ 1000).
• Dòng thứ hai chứa n số nguyên dương p₁, p₂, ..., p_n (0 < p_i ≤ 10000).
• Dòng thứ ba chứa n số nguyên dương d₁, d₂, ..., d_n (0 < d_i ≤ 10000).

Output

• Dòng đầu tiên ghi số lượng công việc bị hoàn thành trễ hạn theo trình tự tìm được.
• Dòng tiếp theo ghi n số nguyên dương là chỉ số của các công việc theo trình tự thực hiện tìm được.

Example

Input:
6
2 4 1 2 3 1
3 5 6 6 7 8

Output:
2
1 3 4 6 2 5