The time complexity could be a polynomial.

Somewhere near the Algorithmville, a number of frogs are standing on a number of lotus leaves. As they are social animals (and yes, they are never infected by coronavirus!), the frogs would like to gather together, all on the same lotus leaf. The frogs do not want to get wet, so they have to use their limited jump distance d to get together by jumping from piece to piece. However, these lotus leaves just started to grow, they will get damaged further by the force needed to jump to another leaf. Fortunately, the frogs are real experts on leaves, and know exactly how many times a frog can jump off each leaf before it sinks and become unavailable. Landing on leaves does not damage it. You have to help the frogs find a leaf where they can meet.

In this question, we will get the position of N lotus leaves. For each i ∈ [N], we know its position (xi, yi), the number of frogs ni on that leaf and the number of jumps mi before it sinks. The distance between two leaves (xi, yi) and (xj , yj ) is defined as |xi − xj | + |yi − yj |. Design a polynomial algorithm to determine whether each lotus leaf can hold all frogs for a party. The output is an array with length N, containing yes/no solution. Prove the correctness of your algorithm.