P16939 Postscript

:::info[Problem Background] Everything in Rozema Mining Town was still as familiar as in memory. The evening sky was slowly getting darker. The glow of the furnace fire spilled through the gaps of the stone house windows on both sides of the street, coating the rough black-stone road with a warm and quiet orange color. In the distance, the smelter was still belching gray-white smoke, and the air was filled with the mixed smell of ore sand, coal fire, and hot iron. From the street corner came the echo of hammers striking, again and again, steady like some everyday routine that had never changed. The ores piled under the eaves waiting to be sorted, the shopfronts with thick cloth curtains hanging by the doors, and the fine dust kicked up when pedestrians’ boots stepped over the stone slabs were all almost the same as when they first came here. Frieren and her companions finally returned here. Back to the place where they had set off, and back to the old shop that sold “magic-storing stones” (jumoshi). When they pushed the door open, the old copper bell hanging on the doorframe rang softly once. The shop was still filled with all kinds of ores and half-polished crystals. The small lamp behind the counter, which was never put out all year round, was still lit. The dim yellow light fell on the wooden cabinets and stone surfaces, making the whole shop look a bit old, yet especially reassuring. “Welcome—ah, it’s you.” The owner looked up. After seeing who it was, he immediately showed a somewhat surprised expression. “Didn’t you just buy so many magic-storing stones yesterday?” As he spoke, he wiped the ore dust off his hands. “So, did they come in handy?” “They were extremely useful—” Fern almost instinctively picked up the conversation. She took that string of magic-storing stones out of her bag. Her fingertips gently brushed over the quiet stones that faintly glowed, and a complicated yet soft look rose in her eyes. “If we didn’t have them, we probably—” “Aren’t they not used at all?” The owner leaned in for a look and immediately cut her off. In that string of magic-storing stones, the magic they had personally infused earlier was still completely and steadily sealed inside, with no sign of being consumed at all. Each stone was as calm as when it had been bought, as if it had never really been used from start to finish. The owner immediately showed an “as expected” expression and could not help shaking his head. “You spent so much money, and in the end they still weren’t useful.” Fern froze for a moment, not knowing how to explain. She lowered her head to look at those magic-storing stones, yet it was as if the deafening roars deep in the library were sounding in her ears again, and before her eyes flashed scenes of battles, mechanisms, corridors, and splendid old sights that time had long since smoothed over. They had clearly gone through so much, but on this correct timeline, all evidence had been quietly taken back, leaving only themselves to remember. Frieren, standing to the side, smiled softly. “They really were useful.” She said calmly. “But in the future.” “...What?” The owner was stunned, with a completely confused expression on his face. Frieren did not explain further. In fact, there was no need to explain anymore. The deal had long been completed. For the owner, the magic-storing stones were sold, and the money was received, and that was enough. As for whether these three people had really taken them into some ancient library sealed by time, whether they had met the grand librarian from a thousand years ago, whether they had briefly stepped onto an incorrect timeline that had been rewritten, and whether they had personally put everything back into place—those things would, in the end, only remain in their own memories, like an adventure so dreamlike that it was almost impossible to tell others. And just then, a noisy commotion suddenly came from outside the shop. The sound of wooden wheels rolling over the stone road, the echoes of workers shouting to one another, and the dull thud of something heavy being set down came in from outside the door one after another. The owner immediately leaned out to take a look, then seemed to remember something. His face changed, and he hurriedly put the cloth in his hand onto the counter. “Ah, so my newly bought cabinet has arrived!” He hurried around from behind the counter. As he ran outside, he waved to the street. “Over here, over here! Move it here first!” ## 题目描述

The owner is assembling a cabinet. Since he wants the cabinet to hold more ore, he wants to install some support modules on the cabinet. The owner ordered $n$ support modules, numbered $1\sim n$. Each support module $i$ has its own weight $w_i$ and supporting capacity $s_i$. Because it takes time for the support modules to be delivered to the old shop, module $i$ can only arrive on day $t_i$. Also, at most one support module arrives each day; that is, for any two support modules $i$ and $j$, it is guaranteed that $t_i\neq t_j$. After a support module arrives, workers will install it on the cabinet immediately, so it cannot be returned after it arrives. The owner found that some support modules are too heavy and will crush the cabinet. Specifically, when $$\sum_{\text{installed modules}}w_i>\sum_{\text{installed modules}}s_i$$ the cabinet will be crushed. The owner does not want his cabinet to be crushed, so he decides to cancel some modules before they arrive. Since canceling requires paying a penalty fee, he wants to know the minimum number of modules that must be canceled to ensure the cabinet will not be crushed.

The first line contains an integer $n(1\leq n\leq 2\times 10^5)$, representing the number of support modules the owner ordered. The following $n$ lines each contain three integers $w_i, s_i, t_i(1\leq w_i, s_i, t_i\leq 10^9)$, representing the weight, supporting capacity, and arrival time of the $i$-th support module. The testdata guarantees that all arrival times are different.

Output one line containing an integer, representing the minimum number of modules the owner needs to cancel.

It is enough to cancel only the $4$-th support module. The remaining modules will arrive and be installed in the order of IDs $2, 6, 1, 5, 3$. In this case, the cabinet will not be crushed, and it is not hard to prove that there is no solution with fewer cancellations. :::info[Problem Background] --- After that, Frieren and her companions did not leave Rozema Mining Town immediately. Perhaps because they had experienced too many things, even though on the correct timeline everything had returned to normal, the scenery they truly saw and the choices they truly made still needed a bit of time to slowly sink into their hearts. So they stayed quietly in this small town, which was always filled with the smell of furnace fire and ore dust, for a few more days. Life in the mining town was still not very different from when they first arrived. In the early morning, when the first light fell on the mountain ridge, the smelters in the town would light up one after another. Gray-white smoke passed between rooftops and tall towers, slowly rising into the still chilly sky. There were always craftsmen and miners walking back and forth on the streets early, their boots stepping on the black stone road with steady, rhythmic sounds. By evening, the echoes of hammers striking ore would layer upon layer under alleys and eaves, and the lamps at shop doors would light up one by one, making the whole town warm and plain. Fern seemed to quickly get used to this quiet life again. Early in the day, she would help sort out the somewhat messy luggage from the journey, putting staffs, scrolls, dry rations, and spare clothes back in order one by one. She would also go to shops in town to pick small items that might be useful on the road—sometimes needles and thread, sometimes portable seasonings, and sometimes simply because “it might be needed later.” When passing dessert stalls, she would also stop briefly and seriously compare which one was made more delicately. At night, she often sat by the inn window and recopied what she had seen and heard along the way under the lamplight. Those memories about forests, libraries, ancient techniques, and time were written down by her very quietly on paper, as if she did not want them to fade easily. Stark quickly became familiar with the people in the mining town. Sometimes he would be called to help move newly arrived ore and cabinets. Even though he was only lending a hand temporarily, he would often make people around him stare blankly because he was too strong. Others would bring him to look at newly forged weapons, asking whether the weight felt good and whether the length was suitable. Although he often wore an expression like “why are you asking me this,” in the end he would still give his opinion very seriously. When he was occasionally free, he would sit outside the ice dessert shop at the town entrance, holding a cup bigger than his face and staring into space. Once Fern asked what he was thinking about. He scratched his head and said that the ice dessert here was not quite the same as what his master used to take him to eat, but it was still pretty good. As for Frieren, she looked no different from usual. She would still sit on a bench in front of the inn or by the square in the best afternoon sunlight, quietly reading magic books. Sometimes she would also slowly walk between secondhand stalls and ore shops, as if looking for some inconspicuous yet worth-taking small magic. Sometimes she would look up at the cooking smoke slowly drifting up over the mining town, her gaze staying for a long time, yet she would not say what she was thinking. Only Fern would occasionally notice that Frieren’s fingers would unconsciously touch the place on her chest where she used to keep books, as if she still remembered that a “Book of Time” that should not truly be taken away by anyone had once been placed there briefly. But in the end, she did not say anything. Some things, for Frieren, were probably always like this—see them, remember them, and then keep moving forward. During those days of staying, they also passed by that old shop selling magic-storing stones again. The owner was still busy: checking accounts, inspecting goods, and arguing with workers about which batch of ore had better quality. When he occasionally caught sight of the three of them, he would only casually greet them and ask where they planned to go next. To him, they were probably just three travelers passing through the mining town who had bought quite a lot of magic-storing stones. But precisely because of that, this unknown secret felt especially real—as if that long journey across the library and time had truly been neatly folded up, hidden only in the shared memory of the three of them. A few days later, the weather finally cleared again. The clouds on the mountain ridge were blown away by the morning wind, and the distant sky showed a clear and bright blue. The town bell rang slowly, and there were more pedestrians on the streets. The wheels carrying ore rolled over the stone slabs, making a low and familiar sound. In front of the inn, Fern had already tied the last package, and Stark had also shouldered his weapon and luggage again. Frieren stood at the front. Her silver-white long hair lifted gently in the wind, and her eyes went past the small road at the end of the mining town that led into the distance, quietly looking toward the next part of the journey that had not yet been reached. They had already seen the stagnant time deep in the ancient library, seen the rewritten world, and personally returned everything to where it should have stayed. But the journey never stops because a legend ends. Beyond the mountains there were new roads; after the forests there were new towns. The blank spaces on the map that they had not yet walked to were still quietly waiting for those who came later. Fern walked to Frieren’s side and softly breathed out. Stark raised his hand to block the morning light and also stood still. After a brief silence, Frieren turned back and looked at them. “Let’s go.” --- “Is it over?” “Yes, it’s over.” “Frieren will have more adventures in the future, right? She will experience so, so many things and meet so, so many people. Just thinking about it is exciting!” “Yes. But it’s already late. Next time, if we have a chance, I’ll tell you again. We need to get ready to sleep.” “Good night!” “Good night. Sweet dreams.” ::: Translated by ChatGPT 5