One Sunday Petr went to a bookshop and bought a new book on sports programming. The book had exactly n pages.
Petr decided to start reading it starting from the next day, that is, from Monday. Petr's got a very tight schedule and for each day of the week he knows how many pages he will be able to read on that day. Some days are so busy that Petr will have no time to read whatsoever. However, we know that he will be able to read at least one page a week.
Assuming that Petr will not skip days and will read as much as he can every day, determine on which day of the week he will read the last page of the book.
The first input line contains the single integer n (1 ≤ n ≤ 1000) — the number of pages in the book.
The second line contains seven non-negative space-separated integers that do not exceed 1000 — those integers represent how many pages Petr can read on Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday correspondingly. It is guaranteed that at least one of those numbers is larger than zero.
Print a single number — the number of the day of the week, when Petr will finish reading the book. The days of the week are numbered starting with one in the natural order: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.
100
15 20 20 15 10 30 45
6
2
1 0 0 0 0 0 0
1
Note to the first sample:
By the end of Monday and therefore, by the beginning of Tuesday Petr has 85 pages left. He has 65 pages left by Wednesday, 45 by Thursday, 30 by Friday, 20 by Saturday and on Saturday Petr finishes reading the book (and he also has time to read 10 pages of something else).
Note to the second sample:
On Monday of the first week Petr will read the first page. On Monday of the second week Petr will read the second page and will finish reading the book.
Having bought his own apartment, Boris decided to paper the walls in every room. Boris's flat has n rooms, each of which has the form of a rectangular parallelepiped. For every room we known its length, width and height of the walls in meters (different rooms can have different dimensions, including height).
Boris chose m types of wallpaper to paper the walls of the rooms with (but it is not necessary to use all the types). Each type of wallpaper is sold in rolls of a fixed length and width (the length, naturally, shows how long the unfolded roll will be). In addition, for each type we know the price of one roll of this type.
The wallpaper of each type contains strips running along the length of the roll. When gluing the strips must be located strictly vertically (so the roll cannot be rotated, even if the length is less than the width). Besides, a roll can be cut in an arbitrary manner, but the joints of glued pieces should also be vertical. In addition, each room should be papered by only one type of wallpaper. And pieces of the same roll cannot be used to paper different rooms. That is, for each room the rolls are purchased separately. Also, some rolls can be used not completely.
After buying an apartment Boris is short of cash, so he wants to spend the minimum money on wallpaper. Help him.
The first line contains a positive integer n (1 ≤ n ≤ 500) — the number of rooms in Boris's apartment.
Each of the next n lines contains three space-separated positive integers — the length, width and height of the walls in a given room in meters, respectively.
The next line contains a positive integer m (1 ≤ m ≤ 500) — the number of available wallpaper types.
Each of the following m lines contains three space-separated positive integers — the length and width in meters of a given wallpaper and the price of one roll, respectively.
All numbers in the input data do not exceed 500. It is guaranteed that each room can be papered using these types of wallpaper.
Print a single number — the minimum total cost of the rolls.
1
5 5 3
3
10 1 100
15 2 320
3 19 500
640
Note to the sample:
The total length of the walls (the perimeter) of the room is 20 m.
One roll of the first type can be cut into pieces to get three vertical 1 meter wide strips, ergo you need 7 rolls of this type, the price equals 700.
A roll of the second type can be cut into pieces to get five 2 meter wide strips, we need 2 rolls, the price is 640.
One roll of the third type can immediately paper 19 meters out of 20, but we cannot use other types and we have to buy a second roll, the price is 1000.
Vera adores poems. All the poems Vera knows are divided into quatrains (groups of four lines) and in each quatrain some lines contain rhymes.
Let's consider that all lines in the poems consist of lowercase Latin letters (without spaces). Letters "a", "e", "i", "o", "u" are considered vowels.
Two lines rhyme if their suffixes that start from the k-th vowels (counting from the end) match. If a line has less than k vowels, then such line can't rhyme with any other line. For example, if k = 1, lines commit and hermit rhyme (the corresponding suffixes equal it), and if k = 2, they do not rhyme (ommit ≠ ermit).
Today on a literature lesson Vera learned that quatrains can contain four different schemes of rhymes, namely the following ones (the same letters stand for rhyming lines):
- Clerihew (aabb);
- Alternating (abab);
- Enclosed (abba).
If all lines of a quatrain pairwise rhyme, then the quatrain can belong to any rhyme scheme (this situation is represented by aaaa).
If all quatrains of a poem belong to the same rhyme scheme, then we can assume that the whole poem belongs to this rhyme scheme. If in each quatrain all lines pairwise rhyme, then the rhyme scheme of the poem is aaaa. Let us note that it doesn't matter whether lines from different quatrains rhyme with each other or not. In other words, it is possible that different quatrains aren't connected by a rhyme.
Vera got a long poem as a home task. The girl has to analyse it and find the poem rhyme scheme. Help Vera cope with the task.
The first line contains two integers n and k (1 ≤ n ≤ 2500, 1 ≤ k ≤ 5) — the number of quatrains in the poem and the vowel's number, correspondingly. Next 4n lines contain the poem. Each line is not empty and only consists of small Latin letters. The total length of the lines does not exceed 104.
If we assume that the lines are numbered starting from 1, then the first quatrain contains lines number 1, 2, 3, 4; the second one contains lines number 5, 6, 7, 8; and so on.
Print the rhyme scheme of the poem as "aabb", "abab", "abba", "aaaa"; or "NO" if the poem does not belong to any of the above mentioned schemes.
1 1
day
may
sun
fun
aabb
1 1
day
may
gray
way
aaaa
2 1
a
a
a
a
a
a
e
e
aabb
2 1
day
may
sun
fun
test
hill
fest
thrill
NO
In the last sample both quatrains have rhymes but finding the common scheme is impossible, so the answer is "NO".
Andrey's favourite number is n. Andrey's friends gave him two identical numbers n as a New Year present. He hung them on a wall and watched them adoringly.
Then Andrey got bored from looking at the same number and he started to swap digits first in one, then in the other number, then again in the first number and so on (arbitrary number of changes could be made in each number). At some point it turned out that if we sum the resulting numbers, then the number of zeroes with which the sum will end would be maximum among the possible variants of digit permutations in those numbers.
Given number n, can you find the two digit permutations that have this property?
The first line contains a positive integer n — the original number. The number of digits in this number does not exceed 105. The number is written without any leading zeroes.
Print two permutations of digits of number n, such that the sum of these numbers ends with the maximum number of zeroes. The permutations can have leading zeroes (if they are present, they all should be printed). The permutations do not have to be different. If there are several answers, print any of them.
198
981
819
500
500
500
One day Natalia was walking in the woods when she met a little mushroom gnome. The gnome told her the following story:
Everybody knows that the mushroom gnomes' power lies in the magic mushrooms that grow in the native woods of the gnomes. There are n trees and m magic mushrooms in the woods: the i-th tree grows at a point on a straight line with coordinates ai and has the height of hi, the j-th mushroom grows at the point with coordinates bj and has magical powers zj.
But one day wild mushroommunchers, the sworn enemies of mushroom gnomes unleashed a terrible storm on their home forest. As a result, some of the trees began to fall and crush the magic mushrooms. The supreme oracle of mushroom gnomes calculated in advance the probability for each tree that it will fall to the left, to the right or will stand on. If the tree with the coordinate x and height h falls to the left, then all the mushrooms that belong to the right-open interval [x - h, x), are destroyed. If a tree falls to the right, then the mushrooms that belong to the left-open interval (x, x + h] are destroyed. Only those mushrooms that are not hit by a single tree survive.
Knowing that all the trees fall independently of each other (i.e., all the events are mutually independent, and besides, the trees do not interfere with other trees falling in an arbitrary direction), the supreme oracle was also able to quickly calculate what would be the expectation of the total power of the mushrooms which survived after the storm. His calculations ultimately saved the mushroom gnomes from imminent death.
Natalia, as a good Olympiad programmer, got interested in this story, and she decided to come up with a way to quickly calculate the expectation of the sum of the surviving mushrooms' power.
The first line contains two integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 104) — the number of trees and mushrooms, respectively.
Each of the next n lines contain four integers — ai, hi, li, ri (|ai| ≤ 109, 1 ≤ hi ≤ 109, 0 ≤ li, ri, li + ri ≤ 100) which represent the coordinate of the i-th tree, its height, the percentage of the probabilities that the tree falls to the left and to the right, respectively (the remaining percentage is the probability that the tree will stand on).
Each of next m lines contain two integers bj, zj (|bj| ≤ 109, 1 ≤ zj ≤ 103) which represent the coordinate and the magical power of the j-th mushroom, respectively.
An arbitrary number of trees and mushrooms can grow in one point.
Print a real number — the expectation of the total magical power of the surviving mushrooms. The result is accepted with relative or absolute accuracy 10 - 4.
1 1
2 2 50 50
1 1
0.5000000000
2 1
2 2 50 50
4 2 50 50
3 1
0.2500000000
It is believed that the mushroom with the coordinate x belongs to the right-open interval [l, r) if and only if l ≤ x < r. Similarly, the mushroom with the coordinate x belongs to the left-open interval (l, r] if and only if l < x ≤ r.
In the first test the mushroom survives with the probability of 50%, depending on where the single tree falls.
In the second test the mushroom survives only if neither of the two trees falls on it. It occurs with the probability of 50% × 50% = 25%.
Pretest №12 is the large test with 105 trees and one mushroom.